本文主要是介绍POJ-2186 Popular Cows 强连通 + 缩点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://poj.org/problem?id=2186
我们求强连通分量时，给每个顶点做一个标记，标记该顶点属于哪个强联通分量，然后属于同一个强连通分量的点就可以看作同一个点了。这就是所谓的“缩点”
此题用了个定理 ：有向无环图（DAG）中，从任意一个点出发，必定可以到达某一个出度为0的点。
这个不用证明，直观想一下就行了。 因为无环，所以从一个点出发，必定会到达终点，终点的出度即是0
求强连通的目的也就是将原图改造成一个DAG，因为将属于同一强连通分支的看作一点后，这个新图就是一个DAG
我们统计DAG中出度为0的个数，如果大于1,说明出度为0的“点”不止一个，也就没有题目中要求的能够被其他所有点到达的点。
如果出度为0的“点”（强连通分支），只有一个，那么该强连通分支中所有的点即可被剩下的点到达。该分支点的个数即是答案。
#include<stdio.h>
#include<string.h>
#include<queue>
#include<vector>
#include<stack>
using namespace std;
const int maxn = 10005;
const int inf = 1<<30;
int n,m;
int dfs_clock,scc_cnt;
int dfn[maxn],low[maxn],sccno[maxn];
vector<int>map[maxn];
stack<int>S;
void dfs( int u,int fa )
{S.push(u);dfn[u] = low[u] = ++dfs_clock;for( int i = 0; i < map[u].size(); i ++ ){int v = map[u][i];if( !dfn[v] ){dfs(v,u);low[u] = low[u] <= low[v] ? low[u] : low[v];}else if( !sccno[v] ){low[u] = low[u] <= dfn[v] ? low[u] : dfn[v];}}if( low[u] == dfn[u] ){scc_cnt ++;for(;;){int x = S.top(); S.pop();sccno[x] = scc_cnt;if( x == u )break;}}
}
void tarjan()
{dfs_clock = scc_cnt = 0;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(sccno,0,sizeof(sccno));for( int i = 1; i <= n; i ++ )if( !dfn[i] )dfs(i,-1);
}
void fun()
{bool mark[maxn] = {0};tarjan();for( int i = 1; i <= n; i ++ ){ //标记有出度的点for( int j = 0; j < map[i].size(); j ++ ){if( sccno[i] != sccno[map[i][j]] ){mark[sccno[i]] = true;break;}}}int flag = 0,p; //找出度为0的点for( int i = 1; i <= scc_cnt; i ++ ){if( !mark[i] ){flag ++;p = i;}}if( flag > 1 )puts("0");else{int ans = 0;for( int i = 1; i <= n; i ++ )if( sccno[i] == p )ans ++;printf("%d\n",ans);}
}
int main()
{//freopen("data.txt","r",stdin);int u,v;while( scanf("%d%d",&n,&m) == 2 ){for( int i = 1; i <= m; i ++ ){scanf("%d%d",&u,&v);map[u].push_back(v);}fun();}return 0;
}这篇关于POJ-2186 Popular Cows 强连通 + 缩点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
