POJ2186 Popular Cows（强连通分量）

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

题意：

奶牛A觉得奶牛B流行，奶牛B觉得奶牛C流行，则奶牛A也觉得奶牛C流行，现在要统计被其他所有奶牛觉得流行的奶牛数量。

要点：

先求出强连通分量并缩成点，算出对应入度和出度，统计出度为0的奶牛数即可，一开始我是统计进度为cnt-1的，后来发现WA，错误的地方在题目里也说了，A->B->C这种也认为A觉得C流行，所以不能用入度算，只能计算出度为0的点，而且如果有好几个点出度为0要输出0

16068699

Seasonal

2186

Accepted

1240K

469MS

C++

1562B

2016-09-09 10:21:14

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<stack>
using namespace std;
const int maxn=1e4+5;
vector<int> g[maxn];
stack<int> s;
int dfn[maxn],low[maxn],belong[maxn];
bool instack[maxn];
int in0[maxn],out0[maxn];
int dfs_clock,cnt,n,m;void dfs(int u)
{dfn[u]=low[u]=++dfs_clock;s.push(u);instack[u]=true;for(int i=0;i<g[u].size();i++){int v=g[u][i];if(!dfn[v])//如果v还没搜索过要先搜索这个点，因为它的low会改变 {dfs(v);low[u]=min(low[u],low[v]);//回溯时改变u的low }else if(instack[v])//如果v已经搜索过且已经在栈中，说明v到u有一条反向边 {low[u]=min(low[u],dfn[v]);//v为u的祖先，low存储v的dfn值	}}if(low[u]==dfn[u])//相等则说明最远祖先是自己，说明自己是第一个节点 {cnt++;for(;;){int x=s.top();s.pop();belong[x]=cnt;instack[x]=false;if(x==u)break;}}
}
void Tarjan()
{dfs_clock=cnt=0;memset(instack,false,sizeof(instack));memset(dfn,0,sizeof(dfn));for(int i=1;i<=n;i++)if(!dfn[i])dfs(i);
}int main()
{while(scanf("%d%d",&n,&m)!=EOF){for(int i=1;i<=n;i++)//注意这里每次要清空g[i].clear();int u,v;for(int i=1;i<=m;i++){scanf("%d%d",&u,&v);g[u].push_back(v);}Tarjan();for(int i=1;i<=n;i++)in0[i]=out0[i]=0;for(int u=1;u<=n;u++)for(int i=0;i<g[u].size();i++){int v=g[u][i];if(belong[u]!=belong[v]){in0[belong[v]]++;out0[belong[u]]++;}}/*int sum=0;for(int i=1;i<=cnt;i++){if(in0[i]==cnt-1){for(int j=1;j<=n;j++)if(belong[j]==i)sum++;}	}printf("%d\n",sum);*/int sum=0,count=0;for(int i=1;i<=cnt;i++){if(out0[i]==0){count++;for(int j=1;j<=n;j++)if(belong[j]==i)sum++;}	}if(count>1)printf("0\n");else if(count==1)printf("%d\n",sum);}return 0;
}

这篇关于POJ2186 Popular Cows（强连通分量）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---