1051: [HAOI2006]受欢迎的牛
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 3134 Solved: 1642
[Submit][Status][Discuss]
Description
每一头牛的愿望就是变成一头最受欢迎的牛。现在有N头牛，给你M对整数(A,B)，表示牛A认为牛B受欢迎。 这种关系是具有传递性的，如果A认为B受欢迎，B认为C受欢迎，那么牛A也认为牛C受欢迎。你的任务是求出有多少头牛被所有的牛认为是受欢迎的。
Input
第一行两个数N,M。 接下来M行，每行两个数A,B，意思是A认为B是受欢迎的（给出的信息有可能重复，即有可能出现多个A,B）
Output
一个数，即有多少头牛被所有的牛认为是受欢迎的。
Sample Input
3 3
1 2
2 1
2 3
1 2
2 1
2 3
Sample Output
1
HINT
100%的数据N<=10000,M<=50000
很久之前做过的一道题目。。
具体就是先tarjan缩点，点的权值就是这个连通分量的点的数量
然后找入度为0的点
只有一个就输出它的权值
多个就输0
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath> #define maxn 10001 using namespace std; inline int In()
{
int x=;char ch=getchar();
while(ch<''||ch>'')ch=getchar();
while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();
return x;
} struct ed{
int u,v;
}edge[maxn*]; struct node{
int to,last;
}e[maxn*]; int last[maxn],tot=,dfn[maxn],low[maxn],father[maxn],sta[maxn],top=,cnt=,size=,num[maxn],in[maxn]; bool ins[maxn]; void add(int u,int v){e[++tot].to=v,e[tot].last=last[u],last[u]=tot;} void tarjan(int poi)
{
dfn[poi]=low[poi]=++cnt;
ins[poi]=;sta[++top]=poi;
for(int i=last[poi];i;i=e[i].last)
{
int u=e[i].to;
if(!dfn[u])
{
tarjan(u);
low[poi]=min(low[u],low[poi]);
}
else if(ins[u]) low[poi]=min(low[poi],dfn[u]);
}
if(dfn[poi]==low[poi])
{
size++;
int vv;
do{
vv=sta[top];
father[vv]=size;
ins[vv]=;
num[size]++;
top--;
}while(vv!=poi);
}
} int main()
{
freopen("1051.in","r",stdin);
int n,m,str=;
n=In(),m=In();
for(int i=;i<=n;i++)father[i]=i;
for(int i=;i<=m;i++)
edge[i].u=In(),edge[i].v=In(),add(edge[i].u,edge[i].v);
for(int i=;i<=n;i++)if(!dfn[i])tarjan(i);
memset(last,,sizeof(last));
tot=;
for(int i=;i<=m;i++)if(father[edge[i].u]!=father[edge[i].v]){
in[father[edge[i].u]]++;
}
for(int i=;i<=size;i++)
{
if(!in[i]&&str){printf("");return ;}
if(!in[i])str=i;
}
printf("%d",num[str]);
return ;
}