tarjan找有向图强连通分量

2024-02-28 12:08:58

tarjan找强连通分量

有向图强连通分量

在有向图G中，如果两个顶点vi,vj间（vi>vj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量。

tarjan找强连通算法

算法思想

首先，一个强连通分量形成一个环，或者是一个单点。
如何知道这个环上的某个点呢？即让这个点在dfs中被遍历到两次即可。
我们知道，图可以用dfs遍历，且dfs采用了“栈”的思想，可以用栈实现对强连通分量上的点的保存。一个点及其子孙中存在极大强连通分量，当且仅当该点是其与子孙各点中dfs序最小的那个，否则，若有一个子孙在它之前被遍历到，则能构成一个更大的强连通分量。

具体实现

变量定义

dfn[N]:某个点的dfs序
low[N]:某个点以及其子孙中dfs序最小的值
color[N]:某个点所属的强连通分量的颜色
st[N]:栈，用于储存可能构成强连通分量的点
vis[N]:某个点是否在栈中

代码

void tarjan(int u)
{
    dfn[u]=low[u]=++deep;
    vis[u]=1;
    st[++top]=u;
    int sz=g[u].size();
    for(int i=0;i<sz;i++)
    {
        int v=g[u][i];
        if(!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[v],low[u]);
        }
        else
        {
            if(vis[v])
            low[u]=min(low[v],low[u]);
        }
    }
    if(low[u]==dfn[u])
    {
        vis[u]=0;
        color[u]=++tot;
        while(st[top]!=u)
        {
            vis[st[top]]=0;
            color[st[top]]=tot;
            top--;
        }
        top--;
    }
}

例题：[USACO06JAN]牛的舞会The Cow Prom

给你n个点，m条边，求图中所有大小大于1的强连通分量的个数

输入样例#1：

5 4

2 4

3 5

1 2

4 1

输出样例#1：

1

题解：数出强连通分量的个数，给每个强连通分量染色后，统计每种颜色的数量，输出颜色个数大于1的个数。

#include<cstdio>
#include<vector>
using namespace std;

const int maxn=10010;
int n,m;
int vis[maxn],dfn[maxn],low[maxn],color[maxn],t[maxn];
int deep;
int st[maxn],top;
int tot;

vector<int> e[maxn];

void tarjan(int u)
{
    dfn[u]=++deep;
    low[u]=deep;
    vis[u]=1;
    st[++top]=u;
    int sz=e[u].size();
    for(int i=0;i<sz;i++)
    {
        int v=e[u][i];
        if(!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(vis[v])
            low[u]=min(low[u],low[v]);
    }
    if(dfn[u]==low[u])
    {
        color[u]=++tot;
        vis[u]=0;
        while(st[top]!=u)
        {
            color[st[top]]=tot;
            vis[st[top--]]=0;
        }
        top--;
    } 
}
int ans;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        e[x].push_back(y);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i);
    for(int i=1;i<=n;i++)
        t[color[i]]++;
    for(int i=1;i<=tot;i++)
        if(t[i]>1) ans++;
    printf("%d\n",ans);
    return 0;
}

例题：51nod 1456 小K的技术

给n个点，m个点对(ai,bi)，最初图上无边，要求连最少的边，使得满足这m个点对间ai到bi有路径相连。规定a到b有路，且b到c有路时，a到c也有路。输出最小连边数。

输入样例

4 5

1 2

1 3

1 4

2 3

2 4

输出样例

3

题解：不妨将这m对点当作m条边，建图后，当一个连通块内存在强连通分量时，该连通块内所需边数为连通块点数，若不存在强连通分量，则该连通块所需的边数为连通块点数-1.（可画图验证）

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+10;
int n,m;
int low[maxn],dfn[maxn],tot,deep,st[maxn],top,vis[maxn],num[maxn],color[maxn],t[maxn],tag[maxn],mark[maxn];
vector<int> e[maxn];
int b;
int ans;
int fa[maxn];

int _find(int x)
{
    if(fa[x]==x) return x;
    return fa[x]=_find(fa[x]);
}

void unite(int x,int y)
{
    int fax=_find(x),fay=_find(y);
    if(fax==fay)return ;
    fa[fax]=fay;
}

void tarjan(int u)
{
    low[u]=dfn[u]=++deep;
    vis[u]=1;
    st[++top]=u;
    int sz=e[u].size();
    for(int i=0;i<sz;i++)
    {
        int v=e[u][i];
        unite(u,v);
        if(!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else
        {
            if(vis[v])
            low[u]=min(low[u],low[v]);
        }
    }
    if(low[u]==dfn[u])
    {
        color[u]=++tot;
        vis[u]=0;
        while(st[top]!=u)
        {
            color[st[top]]=tot;
            vis[st[top--]]=0;
            sz++;
        }
        top--;
    }
}


int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        e[x].push_back(y);
    }
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=n;i++) if(!dfn[i])tarjan(i);
    for(int i=1;i<=n;i++) t[color[i]]++;
    for(int i=1;i<=n;i++)
    {
        int fai=_find(i);
        if(t[color[i]]>1) tag[fai]++;
        num[fai]++;
    }
    for(int i=1;i<=n;i++)
    {
        int fai=_find(i);
        if(!mark[fai])
        {
            mark[fai]=1;
            if(tag[fai]) ans+=num[fai];
            else ans+=num[fai]-1;
        }
    }
    printf("%d\n",ans);
    return 0;
}

tarjan缩点

缩点是图论中常用的技巧，当路径上贡献具有传导性时，可以将一个强连通分量缩成一个新点，因为一个强连通分量内的点可以互相到达。强连通分量内的点的个数可以通过染色记录，具有同一种颜色的点的个数即为该强连通分量内点的个数。

例题：poj2186 Popular Cows

告诉你有n头牛，m个崇拜关系，并且崇拜具有传递性，如果a崇拜b，b崇拜c，则a崇拜c，求最后有几头牛被所有牛崇拜。

Sample Input

3 3

1 2

2 1

2 3

Sample Output

1

题解：

先考虑整张图无环时（DAG）的情况，当存在一头牛被所有牛崇拜时，只需考虑出度为0的点的个数（出度为0的点的个数一定大于等于1），若为1，则有解，若大于1，则无解；
若图中有环，则用tarjan将图中强连通分量找出后，对于点u相连的点v，若他们的颜色相同，说明他们处于同一个强连通分量，视作u，v在一个超级点中，不统计在u的出度内；若他们的颜色不同，则说明这两个点属于不同的强连通分量中，即可让u的度数加1.
统计完成后，对于每种颜色（即所有强连通分量）统计度数为0的点，即可得到被所有牛崇拜的“超级点”个数。注意，若该点为点数大于1的强连通分量构成的“超级点”，则要将该强连通分量内的点数加入答案中，而不是加1.

#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;

int n,m;
const int maxn=10010;
int dfn[maxn],low[maxn],cnt[maxn],color[maxn],degree[maxn],vis[maxn];
int tot;
int st[maxn],top;
int tmp,ans;
int deep;
vector<int> g[maxn];

void tarjan(int u)
{
    dfn[u]=++deep;
    low[u]=deep;
    vis[u]=1;
    st[++top]=u;
    int sz=g[u].size();
    for(int i=0;i<sz;i++)
    {
        int v=g[u][i];
        if(!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else
        {
            if(vis[v])
            low[u]=min(low[u],low[v]);
        }
    }
    if(dfn[u]==low[u])
    {
        color[u]=++tot;
        vis[u]=0;
        while(st[top]!=u)
        {
            color[st[top]]=tot;
            vis[st[top--]]=0;
        }
        top--;
    }
}

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        memset(vis,0,sizeof(vis));
        memset(dfn,0,sizeof(dfn));
        memset(color,0,sizeof(color));
        memset(degree,0,sizeof(degree));
        memset(low,0,sizeof(low));
        memset(cnt,0,sizeof(cnt));
        memset(st,0,sizeof(st));
        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++)
        {
            int sz=g[i].size();
            for(int j=0;j<sz;j++)
            {
                int v=g[i][j];
                if(color[i]!=color[v])
                    degree[color[i]]++;
            }
            cnt[color[i]]++;
        }
        for(int i=1;i<=tot;i++)
            if(degree[i]==0) tmp++,ans=cnt[i];
        if(tmp>1) printf("0\n");
        else printf("%d\n",ans); 
    }
    return 0;
}

割点

在一个无向图中，如果有一个顶点集合，删除这个顶点集合以及这个集合中所有顶点相关联的边以后，图的连通分量增多，就称这个点集为割点集合。

割点的求法

由tarjan的算法过程，我们可以得知，若一个点u为割点，则其子孙中必有dfs序比其小的点v，使low[v]<low[u]，在去掉这个点u后，必然让强连通分量中的环上一点去掉，则割掉后的子图不能构成强连通分量。

模板题：洛谷3388

求割点的个数和数量

#include<bits/stdc++.h>
using namespace std;

const int maxn=20010;
int low[maxn],dfn[maxn],iscut[maxn];
int n,m,ans;
vector<int> g[maxn];
int st[maxn],top;
int deep;

void tarjan(int u,int fa)
{
    int child=0;
    int sz=g[u].size();
    dfn[u]=low[u]=++deep;
    for(int i=0;i<sz;i++)
    {
        int v=g[u][i];
        if(!dfn[v])
        {
            child++;
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>dfn[u]) iscut[u]=1;
        }
        else
        {
            if(v!=fa&&dfn[v]<dfn[u]) low[u]=min(low[u],dfn[v]);
        }
    }
    if(fa<0&&child==1) iscut[u]=0;
}


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);
        g[y].push_back(x);
    }
    for(int i=1;i<=n;i++)if(!dfn[i])
        tarjan(i,-1);
    for(int i=1;i<=n;i++) ans+=iscut[i];
    printf("%d\n",ans);
    for(int i=1;i<=n;i++) if(iscut[i]) printf("%d ",i);
    puts("");
    return 0;
}
上一篇：[USACO15DEC] 最大流Max Flow && Tarjan 线性 LCA 教学？


下一篇：10月21日考试 题解（数学+二分答案+动态规划+Tarjan+倍增）