POJ 2186 Popular Cows(强联通分量)

题目链接:http://poj.org/problem?id=2186

题目大意:

   每一头牛的愿望就是变成一头最受欢迎的牛。现在有N头牛,给你M对整数(A,B),表示牛A认为牛B受欢迎。 这
种关系是具有传递性的,如果A认为B受欢迎,B认为C受欢迎,那么牛A也认为牛C受欢迎。你的任务是求出有多少头
牛被所有的牛认为是受欢迎的。
解题思路:
假设有两头牛A和B都被其他所有牛认为是红人,那么显然,A被B认为是红人,B也被A认为是红人,即存在一个包含A、B两个顶点的圈,或者说,A、B同属于一个强联通分量。所以
如果有一头牛被其他所有牛认为是红人,那么其所属的强联通分量内的所有牛都被其他所有牛认为是红人。我们把图进行强联通分量分解后,至多有一个强联通分量满足题目的条件。
做法: 先用tarjan求出每个强连通分量,再缩点,统计每个点的出度,如果有且只有1个出度为0的点,就输出这个点包含的节点数,否则输出0。
代码
 #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
const int N=1e4+; int cnt,num;
int dfn[N],low[N],fa[N],sze[N],outdeg[N];
stack<int>sk;
vector<int>v[N]; void tarjan(int u){
dfn[u]=low[u]=++cnt;
sk.push(u);
for(int i=;i<v[u].size();i++){
int t=v[u][i];
if(!dfn[t]){ //点t未被访问
tarjan(t);
low[u]=min(low[u],low[t]);
}
else if(!fa[t]) low[u]=min(low[u],dfn[t]); //点t已被访问,且t还在栈中
}
if(low[u]==dfn[u]){
num++;
while(){
int t=sk.top();
sk.pop();
fa[t]=num; //缩点操作,将这些点都归为点num
sze[num]++;
if(t==u) break;
}
}
} int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
int a,b;
scanf("%d%d",&a,&b);
v[a].push_back(b);
}
for(int i=;i<=n;i++){
if(!dfn[i]) tarjan(i);
}
for(int i=;i<=n;i++){
for(int j=;j<v[i].size();j++){
int t=v[i][j];
if(fa[t]!=fa[i]) outdeg[fa[i]]++;
}
}
//缩点后,出度为0的点只能有一个,否则不符合条件输出0
int ans=;
for(int i=;i<=num;i++){
if(!outdeg[i]){
if(ans>){
puts("");
return ;
}
ans=sze[i];
}
}
printf("%d\n",ans);
return ;
}
 
 
上一篇:强连通分量分解 Kosaraju算法 (poj 2186 Popular Cows)


下一篇:Web标准中用于改善Web应用程序性能的各种方法总结