强连通分量总结

发布于 2018-05-23  113 次阅读


强连通分量:有向图的一个子图里面的所有点都能互相到达,那么这一个子图被叫做有向图的一个强连通分量,一个点也是一个强连通分量。

求强连通分量的算法之一:tarjan

tarjan的算法实现了对一个强连通分量里面的点都染成相同的颜色,从而实现了把一个强连通分量的里面的点缩成一个点。

例题:poj2553

题意:求一个有向图里面强连通分量的出度为0的所有点,按字典序输出。

代码:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <stack>
#include <vector>
#include <deque>
#include <queue>
#define ri(n) scanf("%d",&n)
#define oi(n) printf("%d\n",n)
#define rl(n) scanf("%lld",&n)
#define ol(n) printf("%lld\n",n)
#define rep(i,l,r) for(i=l;i<=r;i++)
#define rep1(i,l,r) for(i=l;i<r;i++)
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int epg=10-8;
const int maxn=1e4+10;
int low[maxn],dfn[maxn];
int stk[maxn],vis[maxn];
int du[maxn];
vector<int>mp[maxn];
int sum,tt,cnt,co[maxn];
int n,m;
int a[maxn];
void init()
{
    memset(low,0,sizeof(low));
    memset(dfn,0,sizeof(dfn));
    memset(stk,0,sizeof(stk));
    memset(vis,0,sizeof(vis));
    memset(du,0,sizeof(du));
    memset(co,0,sizeof(co));
    memset(a,0,sizeof(a));
    for(int i=0; i<maxn; i++)
        mp[i].clear();
}
void tarjan(int u)
{
    vis[u]=1;
    low[u]=dfn[u]=cnt++;
    stk[++tt]=u;
    for(int i=0; i<mp[u].size(); i++)
    {
        int v=mp[u][i];
        if(vis[v]==0)
            tarjan(v);
        if(vis[v]==1)
            low[u]=min(low[u],low[v]);

    }
    if(dfn[u]==low[u])
    {
        sum++;
        do
        {
            co[stk[tt]]=sum;
            vis[stk[tt]]=-1;
        }
        while(stk[tt--]!=u);
    }
}
void solve()
{
    sum=0,tt=-1,cnt=1;
    for(int i=1; i<=n; i++)
    {
        if(vis[i]==0)
        {
            tarjan(i);
        }
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=0; j<mp[i].size(); j++)
        {
            int v=mp[i][j];
            if(co[i]!=co[v])
                du[co[i]]++;
        }
    }
    int ans=0;
    for(int i=1; i<=sum; i++)
    {
        if(du[i]>0)
            continue;
        for(int j=1; j<=n; j++)
        {
            if(co[j]==i)
                a[ans++]=j;
        }
    }
    sort(a,a+ans);
    for(int i=0; i<ans; i++)
    {
        if(i==ans-1)
            printf("%d",a[i]);
        else
            printf("%d ",a[i]);
    }
    printf("\n");
}
int main()
{
    while(scanf("%d",&n)==1)
    {
        if(!n)
            break;
        scanf("%d",&m);
        init();
        int u,v;
        for(int i=1; i<=m; i++)
        {
            scanf("%d%d",&u,&v);
            mp[u].push_back(v);
        }
        solve();
    }
    return 0;
}

Comments


愿我如星君如月,夜夜流光相皎洁。