强连通分量_牛客博客

若有向图中，u和v之间可以互相到达，则称u，v是强连通的

在有向图G中，如果两点互相可达，则称这两个点强连通，如果G中任意两点互相可达，则称G是强连通图。

定理： 1、一个有向图是强连通的，当且仅当G中有一个回路，它至少包含每个节点一次。

2、非强连通有向图的极大强连通子图，称为强连通分量（SCC即Strongly Connected Componenet）

tarjan算法：

算法思想如下：

　　 dfn[u]表示dfs时达到顶点u的次序号（时间戳），low[u]表示以u为根节点的dfs树中次序号最小的顶点的次序号，所以当dfn[u]=low[u]时，以u为根的搜索子树上所有节点是一个强连通分量。先将顶点u入栈，dfn[u]=low[u]=++idx,扫描u能到达的顶点v，如果v没有被访问过，则dfs(v)，low[u]=min(low[u],low[v])，如果v在栈里，low[u]=min(low[u],dfn[v])，扫描完v以后，如果dfn[u]=low[u]，则将u及其以上顶点出栈。

#include <cstdio>
#include <stack>
#include <cstring>
#include <iostream>
using namespace std;
int n,m,idx=0,k=1,Bcnt=0;
int head[100];
int ins[100]={0};
int dfn[100]={0},low[100]={0};
int Belong[100];
stack <int> s;
struct edge
{
    int v,next;
}e[100];
int min(int a,int b)
{
    return a<b?a:b;
}
void adde(int u,int v)
{
     e[k].v=v;
     e[k].next=head[u];
     head[u]=k++;
}
void readdata()
{
     int a,b;
     memset(head,-1,sizeof(head));
     scanf("%d%d",&n,&m);
     for(int i=1;i<=m;i++)
     {
         scanf("%d%d",&a,&b);
         adde(a,b);
     }
}
void tarjan(int u)
{
     int v;
     dfn[u]=low[u]=++idx;//每次dfs，u的次序号增加1
     s.push(u);//将u入栈
     ins[u]=1;//标记u在栈内
     for(int i=head[u];i!=-1;i=e[i].next)//访问从u出发的边
     {
         v=e[i].v;
         if(!dfn[v])//如果v没被处理过
         {
             tarjan(v);//dfs(v)
             low[u]=min(low[u],low[v]);//u点能到达的最小次序号是它自己能到达点的最小次序号和连接点v能到达点的最小次序号中较小的
         }
         else if(ins[v])low[u]=min(low[u],dfn[v]);//如果v在栈内，u点能到达的最小次序号是它自己能到达点的最小次序号和v的次序号中较小的
     }     
     if(dfn[u]==low[u])
     {
         Bcnt++;
         do
         {
             v=s.top();
             s.pop();
             ins[v]=0;
             Belong[v]=Bcnt;
         }while(u != v);
     }
}
void work()
{
     for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
     printf("\n");
     for(int i = 1;i <= 6;i++)printf("%d %d\n",dfn[i],low[i]);
     printf("共有%d强连通分量，它们是:\n",Bcnt); 
     for(int i=1;i<=Bcnt;i++)
     {
        printf("第%d个:",i);
        for(int j=1;j<=n;j++)
        {
           if(Belong[j]==i)printf("%d ",j);
        }
        printf("\n");
     }
}
int main()
{
    readdata();
    work();
    return 0;
}
/*
6 8 
1 2
1 3
2 4
3 4
3 5
4 1
4 6 
5 6
*/

偷偷看了别人的模板，感觉好罪恶啊

模板题 codevs 1332 上白泽慧音 http://codevs.cn/problem/1332/

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std;

struct node
{
    int v,next;
}t[50010];

int tot,n,m,idx = 0,Bcnt = 0;
int dfn[50010],head[50100],ins[50010],low[50010];
int Belong[50010],g[50010];
stack<int> s;

void add(int u,int v)
{
    tot++;
    t[tot].v = v;
    t[tot].next = head[u];
    head[u] = tot;
}

void tarjan(int u)
{
    dfn[u] = low[u] = ++idx;
    s.push(u);
    ins[u] = 1;
    for(int i = head[u];i != -1; i = t[i].next)
    {
        if(!dfn[t[i].v])
        {
            tarjan(t[i].v);
            low[u] = min(low[u],low[t[i].v]);
        }
        else
            if(ins[t[i].v])
                low[u] = min(low[u],low[t[i].v]);
    }
    int v;
    if(dfn[u] == low[u])
    {
        Bcnt++;
        do
        {
            v = s.top();
            s.pop();
            ins[v] = 0;
            Belong[v] = Bcnt;
        }while(u != v);
    }
}

void work()
{
    for(int i = 1;i <= n; ++i)
        if(!dfn[i]) tarjan(i);
    int ma = 0,mi = 0;
    for(int i = 1;i <= Bcnt; ++i)
    {
        for(int j = 1;j <= n; ++j)
            if(Belong[j] == i) g[i]++;
        if(g[i] > ma)
        {
            ma = g[i];
            mi = i;
        }
    }
    printf("%d\n",ma);
    for(int i = 1;i <= n; ++i)
        if(Belong[i] == mi)
        {
            if(ma--)
            printf("%d ",i);
            else printf("%d\n",i);
        }
}

int main()
{
    memset(head,-1,sizeof(head));
    scanf("%d%d",&n,&m);
    for(int i = 0;i < m; ++i)
    {
        int a,b,z;
        scanf("%d%d%d",&a,&b,&z);
        add(a,b);
        if(z == 2) add(b,a);
    }
    work();
    return 0;
}

洛谷2341 https://www.luogu.org/problemnew/show/P2341

题目描述

每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶

牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果A喜

欢B，B喜欢C，那么A也喜欢C。牛栏里共有N 头奶牛，给定一些奶牛之间的爱慕关系，请你

算出有多少头奶牛可以当明星。

输入输出格式

输入格式：

 第一行：两个用空格分开的整数：N和M

 第二行到第M + 1行：每行两个用空格分开的整数：A和B，表示A喜欢B

输出格式：

 第一行：单独一个整数，表示明星奶牛的数量

输入输出样例

输入样例#1： 复制

输出样例#1： 复制

说明

只有 3 号奶牛可以做明星

【数据范围】

10%的数据N<=20, M<=50

30%的数据N<=1000,M<=20000

70%的数据N<=5000,M<=50000

100%的数据N<=10000,M<=50000

可以想到强连通分量缩点，出度为0的强连通分量的点个数，如果出度为0的强连通分量超过1个，那么就没有明星。

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std;
const int N = 10050;
struct node
{
    int v,next;
}t[N * 20];

int tot,n,m,idx = 0,Bcnt = 0;
int dfn[N],head[N * 20],ins[N],low[N];
int Belong[N],g[N],id[N],du[N];
stack<int> s;

void add(int u,int v)
{
    tot++;
    t[tot].v = v;
    t[tot].next = head[u];
    head[u] = tot;
}

void tarjan(int u)
{
    dfn[u] = low[u] = ++idx;
    s.push(u);
    ins[u] = 1;
    for(int i = head[u];i != -1; i = t[i].next)
    {
        if(!dfn[t[i].v])
        {
            tarjan(t[i].v);
            low[u] = min(low[u],low[t[i].v]);
        }
        else
            if(ins[t[i].v])
                low[u] = min(low[u],low[t[i].v]);
    }
    int v;
    if(dfn[u] == low[u])
    {
        Bcnt++;
        do
        {
            v = s.top();
            s.pop();
            ins[v] = 0;
            Belong[v] = Bcnt;
            id[v] = Bcnt;
            g[Bcnt]++;
        }while(u != v);
    }
}

void work()
{
    for(int i = 1;i <= n; ++i)
        if(!dfn[i]) tarjan(i);
    for(int i = 1;i <= n; ++i)
    {
        for(int j = head[i];j != -1; j = t[j].next)
        {
            if(id[i] != id[t[j].v])
                du[id[i]]++;
        }
    }
    int tt = 0;
    for(int i = 1;i <= Bcnt; ++i)
    {
        if(!du[i])
        {
            if(tt)
            {
                printf("0\n");
                return;
            }
            tt = i;
        }
    }
    printf("%d\n",g[tt]);
}

int main()
{
    memset(head,-1,sizeof(head));
    scanf("%d%d",&n,&m);
    for(int i = 0;i < m; ++i)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
    }
    work();
    return 0;
}

POJ1236

结论：一个有向无环图变成强连通图，最少加边max(a,b), a代表入度为0的点，b代表出度为0的点。

缩点+记录度

#include<iostream>
#include<cstdio>
#include<map>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
using namespace std;

struct node
{
    int v,next;
}t[100000];
int belong[1100],head[1100],dout[1100],din[1100],low[1100],dfn[1100];
stack<int>s;
bool vis[1100];
int tot,x,n,ans,ans1,ans2,idx;

void add(int u,int v)
{
    t[++tot].v = v;
    t[tot].next = head[u];
    head[u] = tot;
}

void tarjan(int u)
{
    low[u] = dfn[u] = ++idx;
    s.push(u);
    vis[u] = 1;
    int v;
    for(int i = head[u];i != -1;i = t[i].next)
    {
        v = t[i].v;
        if(!dfn[v])
        {
            tarjan(v);
            if(low[u] > low[v]) low[u] = low[v];
        }
        else
            if(vis[v] && low[u] > low[v]) low[u] = low[v];
    }
    if(low[u] == dfn[u])
    {
        ans++;
        do
        {
            v = s.top();
            s.pop();
            vis[v] = 0;
            belong[v] = ans;
        }while(u != v);
    }
}

int main()
{
    scanf("%d",&n);
    tot = 0;
    memset(head,-1,sizeof(head));
    for(int i = 1;i <= n; ++i)
    {
        while(1)
        {
            scanf("%d",&x);
            if(!x) break;
            add(i,x);
        }
    }
    idx = ans = 0;
    for(int i = 1;i <= n;++i)
        if(!dfn[i]) tarjan(i);
    for(int i = 1;i <= n; ++i)
    {
        for(int j = head[i];j != -1;j = t[j].next)
        {
            int k = t[j].v;
            if(belong[k] != belong[i])
            {
                din[belong[k]]++;
                dout[belong[i]]++;
            }
        }

    }
    ans1 = ans2 = 0;
    for(int i = 1;i <= ans; ++i)
    {
        if(!din[i]) ans1++;
        if(!dout[i]) ans2++;
    }
    ans2 = max(ans1,ans2);
    if(ans == 1) printf("1\n0\n");
    else printf("%d\n%d\n",ans1,ans2);
    return 0;
}