强连通分量 Kosaraju科萨拉朱算法

    #include<iostream>
    #include<vector>
    
    using namesapce std;
    
    const int NUM = 1e5+5;
    vector<int> G[NUM],rG[NUM];
    int vis[NUM], scnno[NUM];
    vector<int> S;
    int cnt;  //强连通分量的个数
    
    void dfs1(int u){   //dfs 正向图
    	if(vis[u]) return ;   // 已经访问过
    	vis[u] = 1;
    	for( int i = 0; i < G[u].size(); i++) dfs1(G[u][i]);   
    	S.push_back(u);      //深的点标记小
    }
    
    void dfs2(int u){     //dfs 反向
    	if(scnno[u]) return ;    //已经访问过
    	scnno[u]  =1;
    	for(int i = 0; i < rG[u].size(); i++) dfs2(rG[u][i]);
    }
    
    void Kosaraju(int n){
    	S.clear();
    	for(int i = 1; i <=n; i++) dfs1(i);
    	for(int j = n-1; j >= 0;j--) if(!scnno[S[i]]) {cnt++;dfs2(S[i]);}  //从标记点最大的点开始，
    }
    
    
    
    int main(){
    	int n, m, u, v;
    	while(scanf("%d%d",&n, &m),n != 0 || m != 0){
    		for(int i = 0; i < n; i++) G[i] = rG[i] = 0;    //n个点
    		for(int i = 0; i < m; i++){        //m条边
    			scanf("%d%d", &u, &v);
    			G[u].push_back(v);     //正向
    			rG[v].push_back(u);    //反向
    		}
    		Kosaraju(n);
    		printf("%d\n",,cnt);
    
    	}
    
    
    }