有向图的强连通分量

在有向图中，如果2个顶点之间存在至少一条路径，则称这2个顶点强连通。如果有向图G中任意2个顶点都强连通，则称G是一个强连通图。非强连通图有向图的极大强连通子图，称为强连通分量。
强连通分量的求法分为主流的2种，一种是Kosaraju，做2次DFS。另外一种就是伟大的计算机科学家Tarjan发明的算法，该算法只需要做一次DFS即可，比Kosaraju更快。
网上关于Tarjan算法的介绍很多，我推荐Byvoid大牛写的：
有向图强连通分量的Tarjan算法
这篇文章被wiki推荐，非常经典，看完秒懂

一.如何求强连通分量

下面我们先来做一道模板题：

HDU1269 --- 迷宫城堡
分析：Tarjan模板题，看整张图是不是一张强连通图

#include "bits/stdc++.h"
using namespace std;
const int maxn=1e5+100;
struct Edge{
    int to,next;
}edge[maxn];
int n,m,tot,head[maxn];
int low[maxn],dfn[maxn],num[maxn],s[maxn],belong[maxn];
bool Instack[maxn];
int Index,scc,top;
void init(){
    tot=0;
    memset(head,-1,sizeof(head));
    memset(low,0,sizeof(low));
    memset(dfn,0,sizeof(dfn));
    memset(num,0,sizeof(num));
    memset(s,0,sizeof(s));
    memset(belong,0,sizeof(belong));
    memset(Instack,false,sizeof(Instack));
    Index=scc=top=0;
}
void add(int u,int v){
    edge[tot].to=v;edge[tot].next=head[u];head[u]=tot++;
}
void Tarjan(int u){
    int v;
    dfn[u]=low[u]=++Index;
    s[top++]=u;
    Instack[u]=true;
    for(int i=head[u];i!=-1;i=edge[i].next){
        v=edge[i].to;
        if(!dfn[v]){
            Tarjan(v);
            low[u]=min(low[u],low[v]);
        }else if(Instack[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(low[u]==dfn[u]){
        scc++;
        do{
            v=s[--top];
            Instack[v]=false;
            belong[v]=scc;
            num[scc]++;
        }while(u!=v);
    }
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF){
        if(n==0&&m==0) break;
        init();
        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);
        }
        if(scc==1) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

二.Tarjan缩点

其实缩点也是运用Tarjan求强连通分量的方法，不过对于一些贡献具有传导性的问题有时候需要缩点，比如友情传递、路上权值等。
缩点的思想也很显然，因为强连通分量中的每两个点都是强连通的，故可以将一个强连通分量当做一个超级点，而点权按题意来定。
如下图所示就是一个缩点的例子

同样关于缩点问题，我们来看一道简单的模板题

BZOJ1051 --- [HAOI2006]受欢迎的牛
分析：首先对于一个强连通分量里面的所有点都满足条件，于是我们对图进行缩点，这样我们得到的所有点都不是强连通的，现在整张图就是一个DAG。我们考虑出度为0的点，则在图中至少存在一个出度为0的点，如果超过1个，则必不可能满足条件，否则这个点就满足条件。这个点很可能为所有强连通分量构成的超级点，所以也就是要求的也就是这个强连通分量中点的个数

#include "bits/stdc++.h"
using namespace std;
const int maxn=5e4+10;
vector<int>g[maxn];
int n,m;
int low[maxn],dfn[maxn],s[maxn],num[maxn],belong[maxn];
bool Instack[maxn];
int Index,scc,top;
void Tarjan(int u){
    int v;
    low[u]=dfn[u]=++Index;
    s[top++]=u;
    Instack[u]=true;
    for(int i=0;i<g[u].size();i++){
        v=g[u][i];
        if(!dfn[v]){
            Tarjan(v);
            low[u]=min(low[u],low[v]);
        }else if(Instack[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(low[u]==dfn[u]){
        ++scc;
        do{
            v=s[--top];
            Instack[v]=false;
            belong[v]=scc;
            num[scc]++;
        }while(u!=v);
    }
}
int cnt[maxn],du[maxn];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]) Tarjan(i);
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<g[i].size();j++){
            int v=g[i][j];
            if(belong[i]!=belong[v]){
                du[belong[i]]++;
            }
        }
        cnt[belong[i]]++;
    }
    int tmp=0,ans=0;
    for(int i=1;i<=scc;i++){
        if(du[i]==0){
            tmp++;
            ans=cnt[i];
        }
    }
    if(tmp>1) printf("0\n");
    else printf("%d\n",ans);
    return 0;
}

有向图的强连通分量

原文：https://www.cnblogs.com/gzgywh/p/10713358.html