首页 > 其他 > 详细

强连通分量

时间:2019-02-17 14:29:19      阅读:176      评论:0      收藏:0      [点我收藏+]

学习Tarjan

 

受欢迎的牛

因为牛之间的关系具有传递性,所以找出有向图中的强连通子图,每个子图中的牛一定互相喜欢。

$Tarjan$缩点,只有出度为$0$的点(牛)才有可能受到其他所有牛的喜欢(图中已无环)。

如果出度为$0$的点不止$1$个,那么这几个子图中的牛都无法互相喜欢,输出$0$。

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5,M=5e4+5;
int n,m,cnt,top,fro[N],s[N];
int tot,color,dfs[N],low[N],col[N],size[N],in[N];
struct edge{int to,nxt;}e[M];
void add(int x,int y) {
    e[++cnt]={y,fro[x]}; fro[x]=cnt;
}

void Tarjan(int u) {
    dfs[u]=low[u]=++tot;
    s[++top]=u;
    for(int i=fro[u];i;i=e[i].nxt) {
        int v=e[i].to;
        if(!dfs[v]) {
            Tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(!col[v])
         low[u]=min(low[u],dfs[v]);
    }
    if(low[u]==dfs[u]) {
        col[u]=++color;
        while(s[top]!=u) {
            col[s[top--]]=color;
            size[color]++;
        }
        top--,size[color]++;
    }
}

int main() {
    scanf("%d%d",&n,&m);
    for(int i=1,a,b;i<=m;i++) 
     scanf("%d%d",&a,&b),add(b,a); //反向建边,统计出度变为统计入度 
    for(int i=1;i<=n;i++) 
     if(!dfs[i]) Tarjan(i);
     
    for(int i=1;i<=n;i++)
     for(int j=fro[i];j;j=e[j].nxt)
      if(col[i]!=col[e[j].to]) 
       in[col[e[j].to]]++;
    int ans=-1;
    for(int i=1;i<=color;i++)
     if(!in[i]) ans=~ans?0:size[i];
    printf("%d",ans);    
}

 

强连通分量

原文:https://www.cnblogs.com/qq8260573/p/10390928.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!