[HAOI2006]受欢迎的牛（缩点）

题目描述

每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶

牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果A喜

欢B，B喜欢C，那么A也喜欢C。牛栏里共有N 头奶牛，给定一些奶牛之间的爱慕关系，请你

算出有多少头奶牛可以当明星。

输入输出格式

输入格式：

 第一行：两个用空格分开的整数：N和M

 第二行到第M + 1行：每行两个用空格分开的整数：A和B，表示A喜欢B

输出格式：

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

输入输出样例

输入样例#1：

3 3
1 2
2 1
2 3

输出样例#1：

1

说明

只有 3 号奶牛可以做明星

【数据范围】

10%的数据N<=20, M<=50

30%的数据N<=1000,M<=20000

70%的数据N<=5000,M<=50000

100%的数据N<=10000,M<=50000

思路

既然爱慕关系可以传递，那么将互相可达的某几个点缩成一个点，就能简化原图了，

那么很自然想到tarjan求强连通分量

那么就只需找到可以被所有缩点遍历到的那个缩点

再输出它所含的点数就行了

#include<cstdio>
#include<iostream>
using namespace std;
struct node{
int to,next;
}e[50001],d[50001];
int head[10001];
int n,m,cnt,top;
int dfn[10001],low[10001],q[10001];
int scc,h[10001],belong[10001],hav[10001];
bool vis[10001],inq[10001];
int ans;
void dfs(int a)
{
int now;
vis[a]=inq[a]=1;
low[a]=dfn[a]=++cnt;
q[++top]=a;
int c=head[a];
while(c)
{
if(!vis[e[c].to])
{
dfs(e[c].to);
low[a]=min(low[a],low[e[c].to]);
}
else if(inq[e[c].to])low[a]=min(low[a],dfn[e[c].to]);
c=e[c].next;
}
if(low[a]==dfn[a])
{
scc++;
while(now!=a)
{
now=q[top--];
inq[now]=0;
belong[now]=scc;
++hav[scc];
}
}
}
void tarjan()
{
for(int i=1;i<=n;i++)
if(!vis[i])dfs(i);
cnt=0;
for(int i=1;i<=n;i++)
{
int c=head[i];
while(c)
{
if(belong[i]!=belong[e[c].to])
{
d[++cnt].to=belong[e[c].to];
d[cnt].next=h[belong[i]];
h[belong[i]]=cnt;
}
c=e[c].next;
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
e[i].to=y;
e[i].next=head[x];
head[x]=i;
}
tarjan();
for(int i=1;i<=scc;i++)
if(!h[i])
{
if(ans)
{
ans=0;
break;
}
else ans=hav[i];
}
printf("%dn",ans);
return 0;
}

最后

以上就是自觉时光为你收集整理的[HAOI2006]受欢迎的牛（缩点）的全部内容，希望文章能够帮你解决[HAOI2006]受欢迎的牛（缩点）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。