受欢迎的牛 G

受欢迎的牛 G 洛谷

题目描述

每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果 \(A\) 喜欢 \(B\)，\(B\) 喜欢 \(C\)，那么 \(A\) 也喜欢 \(C\)。牛栏里共有 \(N\) 头奶牛，给定一些奶牛之间的爱慕关系，请你算出有多少头奶牛可以当明星。

输入格式

第一行：两个用空格分开的整数：\(N\) 和 \(M\)。

接下来 \(M\) 行：每行两个用空格分开的整数：\(A\) 和 \(B\)，表示 \(A\) 喜欢 \(B\)。

输出格式

一行单独一个整数，表示明星奶牛的数量。

样例输入

3 3
1 2
2 1
2 3

样例输出

1

提示

对于 \(100\%\) 的数据，\(1\le N\le10^4\)，\(1\le M\le5\times 10^4\)。

既然题目出现了喜欢这一关系，那么便可以考虑使用图论算法

对于明星奶牛来说，只有其他所有奶牛都喜欢它，才能成为明星奶牛，换句话来说，就是明星奶牛的出度必定为0

如果出现了两个及以上的奶牛出度为0，那么便说明没有奶牛为明星奶牛，而如果明星奶牛也喜欢别的奶牛，那么这只奶牛也是明星奶牛

到这里已经很明显了，我们可以把所有的强连通分量缩点，找到出度为0的点，打印它的数目，便是明星奶牛的数目

#include<bits/stdc++.h>
using namespace std;
int n,m,cnt,inx,top,ans;
const int N=10005,M=50005;
struct edge{
	int next,to;
}e[M];
int h[N],dfn[N],low[N],stk[N],vis[N],belong[N],sum[N],out[N];

void add(int x,int y){
	e[++cnt]=(edge){h[x],y};
	h[x]=cnt;
}
void Tarjan(int x){
	dfn[x]=low[x]=++inx;
	stk[++top]=x;vis[x]=1;
	for(int i=h[x];i;i=e[i].next){
		int y=e[i].to;
		if(!dfn[y]){
			Tarjan(y);
			low[x]=min(low[x],low[y]);
		}
		else if(vis[y]){
			low[x]=min(low[x],dfn[y]);
		}
	}
	if(low[x]==dfn[x]){
		ans++;int y=0;
		do{
			y=stk[top--];
			vis[y]=0;
			belong[y]=ans;
			sum[ans]++;//由于需要出度与数目，所有要统计每一个强连通分量的数目以及每个强连通分量的编号
		}while(x!=y);
	}
}
int find(){
	int check=0;
	for(int i=1;i<=ans;i++){
		if(out[i]) continue;
		if(check) return 0;//如果有两个及以上的出度为0的点，那么便没有明星奶牛
		check=sum[i];
	}
	return check;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);
	}
	for(int i=1;i<=n;i++) if(!dfn[i]) Tarjan(i);
	for(int i=1;i<=n;i++){
		int x=belong[i];
		for(int j=h[i];j;j=e[j].next){
			int y=e[j].to;
			if(belong[y]!=belong[i]) out[x]++;
		}
	}
	printf("%d",find());
	return 0;
}