算法记录-6-（tarjan-有向图连通性）

tarjan-强连通分量

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int N=100010,M=1000010;
int ver[M],Next[M],head[N],dfn[N],low[N];
int stack[N],ins[N],c[N];
vector<int> scc[N];
int n,m,tot,num,top,cnt;
int hc[N],vc[N<<1],nc[N<<1],tc;
void add(int x,int y){
    ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
}
void add_c(int x,int y){//缩点
    vc[++tc]=y,nc[tc]=hc[x],hc[x]=tc;
}
void tarjan(int x){
    dfn[x]=low[x]=++num;
    stack[++top]=x,ins[x]=1;
    for(int i=head[x];i;i=Next[i])
        if(!dfn[ver[i]]){
            tarjan(ver[i]);
            low[x]=min(low[x],low[ver[i]]);
        }
        else
            if(ins[ver[i]])    low[x]=min(low[x],dfn[ver[i]]);
    if(dfn[x]==low[x]){
        cnt++;
        int y;
        do{
            y=stack[top--],ins[y]=0;
            c[y]=cnt,scc[cnt].push_back(y);
        }while(x!=y);
    }
}
//c[x]表示x所在强连通分量的编号
//scc[i]记录了编号为i的强连通分量中的所有节点
//图***有cnt个强连通分量
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i])    tarjan(i);
    for(int x=1;x<=n;x++)//缩点
        for(int i=head[x];i;i=Next[i]){
            int y=ver[i];
            if(c[x]==c[y])    continue;
            add_c(c[x],c[y]);
        }
    return 0;
}