由 USACO2003 Popular Cows[受歡迎的奶牛] 認識 Tarjan 求強連通分量并縮點

給定N（N<=10000)個點和M（M<=50000)條邊（注意：是有向邊），求有多少個受歡迎的點，當且僅當任何一個點出發都能到達它。

• 這道題可能會有環->縮環成點
• 無環的情況：
  • 1：若有向無環圖是連通的，隻有出度為0的點才是“受歡迎的點”。
  • 2：若有向無環圖是連通的，當存在大于1個出度為0的點，則圖中沒有“受歡迎的點”。
• 尋找出度為0的點，如果不止一個，就沒有答案，否則就是該點

//usaco 2003 popular
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
const int MN=;

int m,n;
vector<int>t[MN];
int outd[MN];//出度 

int low[MN],dfn[MN],vis[MN],sum[MN],blong[MN];
int cnt,cntt;//點 分量 
stack<int>s;
void tar(int x){
    dfn[x]=low[x]=++cnt;
    s.push(x);
    vis[x]=;

    int y;
    for(vector<int>::iterator it=t[x].begin();it!=t[x].end();++it){
        y=*it;
        if(!dfn[y]){//dfn
            tar(y);
            low[x]=min(low[x],low[y]);
        }
        else if(vis[y]){//vis
            low[x]=min(low[x],dfn[y]);//dfn
        }
    }
    if(dfn[x]==low[x]){
        ++cntt;
        do{
            y=s.top();
            s.pop();
            sum[cntt]++;
            blong[y]=cntt;
            vis[y]=;
        }while(y!=x);
    }

}

int main(){
    freopen("popular.in","r",stdin);
    freopen("popular.out","w",stdout);
    cin>>n>>m;
    int ku,kv;
    for(int i=;i!=m;i++){
        cin>>ku>>kv;
        t[ku].push_back(kv);
    }
    for(int i=;i<=n;i++){
        if(!dfn[i]){
            tar(i);
        }
    }
    int flag=;
    for(int i=;i<=n;i++){
        for(vector<int>::iterator it=t[i].begin();it!=t[i].end();++it){
            int j=*it;
            if(blong[i]!=blong[j]){
                outd[blong[i]]++;
            }
        }
    }
    for(int i=;i<=cntt;i++){
        if(!outd[i]){
            if(flag){
                cout<<<<endl;
                return ;
            }
            else flag=i;    
        }   
    }
    if(flag)cout<<sum[flag]<<endl;
    else cout<<<<endl;
    return ;
    fclose(stdin);
    fclose(stdout);
} 
           

有向圖強連通分量的Tarjan算法