poj 2186 Popular Cows 【强连通分量】

3 31 22 12 3
Sample Output
1
Hint
Cow 3 is the only cow of high popularity. 
Source
USACO 2003 Fall

运用强连通分量将图变成DAG图，并知道了最后一个分量可能为拓扑终点，dfs反边搜索看是否达到所有边。

代码：

#include<cstdio>#include<vector>#include<cstring>#include<algorithm>using namespace std;int n,m,cmp[10100];vector<int> V[10100],FV[10100],vs;bool used[10100];void add_edge(int a,int b){    V[a].push_back(b);    FV[b].push_back(a);}void dfs(int v){    used[v]=true;    for (int i=0;i<V[v].size();i++)    {        if (!used[V[v][i]]) dfs(V[v][i]);    }    vs.push_back(v);}void rdfs(int v,int k){    used[v]=true;    cmp[v]=k;    for (int i=0;i<FV[v].size();i++)    {        if (!used[FV[v][i]]) rdfs(FV[v][i],k);    }}int main(){    scanf("%d%d",&n,&m);  //  while (~scanf("%d%d",&n,&m))  //  {        int a,b;      //  for (int i=1;i<=n;i++)      //  {      //      V[i].clear();      //      FV[i].clear();      //  }        vs.clear();        for (int i=0;i<m;i++)        {            scanf("%d%d",&a,&b);            add_edge(a,b);        }        memset(used,0,sizeof(used));        for (int i=1;i<=n;i++)        {            if(!used[i]) dfs(i);        }        memset(used,0,sizeof(used));        int k=1;        for (int i=vs.size()-1;i>=0;i--)        {            if(!used[vs[i]]) rdfs(vs[i],k++);        }        int ans=0;        for (int i=1;i<=n;i++)        {            if (cmp[i]==k-1)            {                m=i;                ans++;            }        }        memset(used,0,sizeof(used));        rdfs(m,0);        for (int i=1;i<=n;i++)        {            if (!used[i])            {                ans=0;                break;            }        }        PRintf("%d/n",ans);    //}    return 0;}