1 solutions
-
1
# include<iostream> using namespace std; const int N=1e4+5,M=1e5+5; struct edge{ int v,next; }e[M]; int head[N],dfn[N],low[N]; int cnt=0,n,m,x,y; int top=0,st[N];//模拟栈 int co[N],col,num=0;//co: 结点i所在强连通分量的编号 bool vis[N]; void add(int x,int y){ e[++cnt].next=head[x]; head[x]=cnt; e[cnt].v=y; } void tarjan(int u){ dfn[u]=low[u]=++num; st[++top]=u;//u入栈 for(int i=head[u];i;i=e[i].next){ int v=e[i].v; if(!dfn[v]){ tarjan(v);//继续向下找 low[u]=min(low[u],low[v]); } //如果v还在栈内,即v不属于任何强连通分量 else if(!co[v]) low[u]=min(low[u],dfn[v]); } if(low[u]==dfn[u]){ co[u]=++col; //将st[top]退栈,其为强连通分量内的一个节点 while(st[top]!=u) co[st[top--]]=col; --top;//将u退栈 } } int main(){ cin>>n>>m; for(int i=0;i<m;++i){ cin>>x>>y; if(x!=y) add(x,y); } for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i); cout<<col<<endl; for(int i=1;i<=n;++i){ if(!vis[i]){ for(int j=i;j<=n;++j) if(co[j]==co[i]){ cout<<j<<" "; vis[j]=1; } cout<<endl; } } }
- 1
Information
- ID
- 6817
- Time
- 1000ms
- Memory
- 512MiB
- Difficulty
- 4
- Tags
- (None)
- # Submissions
- 10
- Accepted
- 7
- Uploaded By