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的强连通分量的节点个数增1 if(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; }