1 solutions

  • 1
    @ 2023-11-30 17:01:08
    # 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