poj 2186 Popular Cows（tarjan + 强连通分量 + 缩点）

本文主要是介绍poj 2186 Popular Cows（tarjan + 强连通分量 + 缩点），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://poj.org/problem?id=2186

题意：有n头牛，m个膜拜关系，膜拜关系是不可逆的而且是单向传递的，比如A膜拜B，B膜拜C,那么A也膜拜C，但B不一定膜拜A。最后问有多少头牛满足条件：除了它自己，其他所有的牛都膜拜它。

思路：

问题可以抽象为：给定一个有向图，n个顶点，m条有向边，有多少个顶点满足：其他所有的点都能到达该点。

首先假如图G是一个有向树，当且仅当它只有一个叶子节点时，树上其他所有的点都能到达该点，而叶子节点数大于1必定不满足。所以我们应构造这样一棵有向无环树（DAG）。

如果原图中有环，那么可以把这个环缩成一个点，因为环中的每个点的“地位”是一样的，无论对环内还是环外，图中的强连通分量也是这样，所以我们可以求出这些强连通分量，把他们分别缩成一个点，然后根据它们在强连通分量中的索引号形成一个新的DAG，这样就形成了一棵有向无环树，判断叶子节点个数是否为1 ，若为1 ，说明有解，而解就是这个缩点（叶子节点）所包含的的节点的数目。

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#include<stack>
using namespace std;
const int maxn =  10010;
const int maxm =  50010;vector <int> edge[maxn];//原图
vector <int> edge2[maxn];//根据强连通分量索引号形成的DAG
int dfn[maxn];
int low[maxn];
int instack[maxn];//标记是否在栈中
int vis[maxn];//标记是否被访问过
int n,m,index;
int cnt;//强连通分量个数
int set[maxn],num[maxn];
stack <int> st;void tarjan(int u)
{dfn[u] = low[u] = ++index;instack[u] = 1;vis[u] = 1;st.push(u);for(int i = 0; i < (int)edge[u].size(); i++){int v = edge[u][i];if(!vis[v])//如果没被访问过，递归访问，并用v的low值来尝试更新u的low值{tarjan(v);low[u] = min(low[u],low[v]);}else if(instack[v])//如果v在栈中，说明v到u有回向边，用v的dfn值来更新u的low值low[u] = min(dfn[v],low[u]);}if(dfn[u] == low[u])//u是强连通分量的根{cnt++;while(1)//一一出栈，直到等于u,那么这几个点组成一个强连通分量{int tmp = st.top();st.pop();instack[tmp] = 0;set[tmp] = cnt;//tmp 所在强连通分量索引号是cnt.num[cnt]++;//索引号是cnt的强连通分量的节点个数增1if(tmp == u)break;}}
}//根据索引号构造一个新的有向无环树DAG
void creat_DAG()
{for(int u = 1; u <= n; u++){for(int i = 0; i < (int)edge[u].size(); i++){int v = edge[u][i];if(set[u] != set[v])edge2[ set[u] ].push_back( set[v] );}}
}//求叶子节点个数并输出
void slove_DAG()
{int count = 0,pos;for(int i = 1; i <= cnt; i++){if(edge2[i].size() == 0){count += 1;pos = i;}}if(count == 1)printf("%d\n",num[pos]);else printf("0\n");
}int main()
{while(~scanf("%d %d",&n,&m)){for(int i = 1; i <= n; i++){edge[i].clear();edge2[i].clear();}int u,v;for(int i = 0; i < m; i++){scanf("%d %d",&u,&v);edge[u].push_back(v);}memset(instack,0,sizeof(instack));memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(num,0,sizeof(num));memset(vis,0,sizeof(vis));while(!st.empty()) st.pop();index = 0;cnt = 0;//注意不一定从任何一点搜索就能遍历到所有点for(int i = 1; i <= n; i++)if(!vis[i])tarjan(i);creat_DAG();slove_DAG();}return 0;
}