SZbr @ 2021-07-15 19:28:23
B3609 [图论与代数结构 701] 强连通分量
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
using namespace std;
int n,m,tot,head[10010],bel[10010],totb,dfn[10010],low[10010],cnt;
bool tost[10010],vis[10010];
stack<int> st;
vector<int> vct[10010];
struct node{
int v,next;
}edge[100010];
void make(int u,int v){
edge[++tot].v=v;
edge[tot].next=head[u];
head[u]=tot;
}
void tarjian(int x){
st.push(x);
tost[x]=true;
dfn[x]=low[x]=++cnt;
for(int i=head[x];i;i=edge[i].next){
if(!dfn[edge[i].v]){
tarjian(edge[i].v);
low[x]=min(low[x],low[edge[i].v]);
}
else if(tost[x]){
low[x]=min(low[x],dfn[edge[i].v]);
}
}
if(low[x]==dfn[x]){
totb++;
while(st.top()^x){
bel[st.top()]=totb;
vct[totb].push_back(st.top());
tost[st.top()]=false;
st.pop();
}
st.pop();
bel[x]=totb;
vct[totb].push_back(x);
tost[x]=false;
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i){
int u,v;
scanf("%d%d",&u,&v);
make(u,v);
}
for(int i=1;i<=n;++i){
if(!dfn[i]){
tarjian(i);
}
}
printf("%d\n",totb);
for(int i=totb;i>=1;--i){
sort(vct[i].begin(),vct[i].end());
// int j;
// for(auto j:vct[i]){
// printf("%d ",j);
// }
// printf("\n");
}
for(int i=1;i<=n;++i){
if(vis[i]) continue;
int j;
for(auto j:vct[bel[i]]){
printf("%d ",j);
vis[j]=true;
}
printf("\n");
}
return 0;
}
by wheneveright @ 2021-07-15 19:32:12
请求开放数据下载 /fn
@SSerxHs
by cyhyyds @ 2021-07-15 19:50:35
数组开太小?
by FoXreign @ 2021-07-19 15:04:30
你的tarjan算法中在枚举每条边时的else if判断条件错了,这时应该是判断edge[i].v是否在栈中,而不是当前节点x
by yizcdl2357 @ 2021-07-28 21:10:14
tarjian
好评