POJ 2186

Tarjan

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
const int maxn=100000+10;
/*
  有n只牛,牛之间存在一些关系,比如a认为b很受欢迎
,b认为c很受欢迎,这样呢,a也会认为c很受欢迎,问根据
给出的关系,有多少头牛被其他所有的牛都认为是受欢迎的?

解:
  对于一个有向无环图来说,其中有且仅有一个点出度为零
,那么这个特殊的点,可以由其他任何点到达。那么接下来我
们直接对所给的图进行强连通分量划分,然后把每个强连通分
量看做一个点,判定出度为零的点有几个,如果有一个就输出
这个点对应的强连通分量含有的节点个数,否则为零。
*/
vector<int> G[maxn];
//lowlink[u] == 为u及其后代能追溯到的最早(最先被发现)的祖先节点v的pre[v]的值.
int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt;

int vis[maxn];

stack<int> S;
//邻接表存储图
void addAdge(int u,int v){
    ///如果点从1开始计数,这里改成-1即可
    G[u-1].push_back(v-1);
}

void dfs(int u){
    pre[u]=lowlink[u]= ++dfs_clock;
    //边dfs将点入栈边Tarjan
    S.push(u);
    for(int i=0;i<G[u].size();++i){
        int v=G[u][i];
        if(!pre[v]){
            dfs(v);
            //回溯时计算lowlink数组
            lowlink[u]=min(lowlink[u],lowlink[v]);
        }else if(!sccno[v]){
            lowlink[u]=min(lowlink[u],pre[v]);
        }
    }
    if(lowlink[u]==pre[u]){
        scc_cnt++;
        for(;;){
            int x=S.top();S.pop();
            sccno[x]=scc_cnt;
            if(x==u)break;
        }
    }
}

void Tarjan(int n){
    dfs_clock=scc_cnt=0;
    memset(sccno,0,sizeof(sccno));
    memset(pre,0,sizeof(pre));
    for(int i=0;i<n;++i){
        if(!pre[i]) dfs(i);
    }
}

int main(){
    //边数
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;++i){
        int u,v;
        cin>>u>>v;
        addAdge(u,v);
    }

    Tarjan(n);

    ///缩点,同一scc缩到同一点中
    for(int i=0;i<n;++i){
        for(int j=0;j<G[i].size();++j){
            ///如果i到G[i][j]这条边不在强连通分量中
            ///说明是一个连接外面的点
            if(sccno[i]!=sccno[G[i][j]]){
                vis[sccno[i]]++;
            }
        }
    }

    int sum=0,ans=0,cnt=0;
    for(int i=1;i<=scc_cnt;++i){
        if(!vis[i]){
            ///如果出度是0,则是一个边界点
            sum++;
            ans=i;
        }
    }
    ///如果只有一个点的话,代表存在一个万人敬仰团体
    if(sum==1){
        for(int i=0;i<n;++i){
            if(sccno[i]==ans){
                cnt++;
            }
        }
        printf("%d\n",cnt);
    }else{
        printf("0\n");
    }
    return 0;
}
/*
3 3
1 2
2 1
2 3

1
*/