1051: [HAOI2006]受欢迎的牛
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 4776 Solved: 2542
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求环的裸题 */
#include<iostream>
#include <cstdio>
#include <cstring>
using namespace std; const int Maxn = ;
const int Maxm = ;
struct node
{
int to,next;
} edge[Maxm];
int n,m,head[Maxn],dfn[Maxn],low[Maxn],stack1[Maxn],num[Maxn],du[Maxn],vis[Maxn],cnt,tt,top,cut; void init()
{
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
memset(head,-,sizeof(head));
memset(vis,,sizeof(vis));
memset(num,,sizeof(num));
memset(du,,sizeof(du));
} void addedge(int u,int v)
{
edge[cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt;
cnt++;
} void Tarjan(int u,int fa)
{
dfn[u]=tt;
low[u]=tt;
tt++;
vis[u]=;
stack1[top]=u;
top++;
for(int i=head[u]; i!=-; i=edge[i].next)
{
int v=edge[i].to;
if(!vis[v])
{
Tarjan(v,u);
low[u]=min(low[u],low[v]);
}
else if(vis[v])
{
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u])
{
cut++;
while(top>&&stack1[top]!=u)
{
top--;
vis[stack1[top]]=;
num[stack1[top]]=cut;
}
}
} int main()
{
int u,v;
while(scanf("%d%d",&n,&m)!=EOF)
{
init();
for(int i=; i<m; i++)
{
scanf("%d%d",&u,&v);
addedge(u,v);
}
for(int i=; i<=n; i++)
{
if(!vis[i])
{
Tarjan(i,);
}
}
for(int i=; i<=n; i++)
{
for(int j=head[i]; j!=-; j=edge[j].next)
{
if(num[i]!=num[edge[j].to])
{
du[num[i]]++;
}
}
}
int sum=,x;
for(int i=; i<=cut; i++)
{
if(!du[i])
{
sum++;
x=i;
}
}
if(sum==)
{
sum=;
for(int i=; i<=n; i++)
{
if(num[i]==x)
{
sum++;
}
}
printf("%d\n",sum);
}
}
return ;
}
心若向阳，无谓悲伤
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=,M=;
int n=,m=;
int head[N],to[M],next[M],edge=;
int dfn[N],inS[N],idx=,low[N];
int stk[N],top=;
int comp[N],n2=,cnt[N];
int in[N];
int head2[N],to2[M],next2[M],edge2=;
int q[N*],front=,back=,vis[N];
inline void addEdge(int u,int v) {
to[edge]=v,next[edge]=head[u],head[u]=edge++;
}
void tarjan(int x) {
dfn[x]=low[x]=idx++;
stk[top++]=x;
inS[x]=;
for (int e=head[x];~e;e=next[e]) {
int& v=to[e];
if (!dfn[v]) {
tarjan(v);
low[x]=min(low[x],low[v]);
} else if (inS[x])
low[x]=min(low[x],dfn[v]);
}
if (dfn[x]==low[x]) {
++n2;
int u=;
do {
u=stk[--top];
comp[u]=n2;
inS[u]=;
++cnt[n2];
} while (u!=x);
}
}
inline void addEdge2(int u,int v) {
++in[v];
to2[edge2]=v,next2[edge2]=head2[u],head2[u]=edge2++;
}
inline void build() {
for (int i=;i<=n;++i)
for (int e=head[i];~e;e=next[e]) {
int &u=comp[i],&v=comp[to[e]];
if (u!=v)
addEdge2(v,u);
}
}
inline int bfs(int s) {
front=back=;
memset(vis,,sizeof(vis));
q[back++]=s;
vis[s]=;
while (front<back) {
int x=q[front++];
for (int e=head2[x];~e;e=next2[e]) {
int& v=to2[e];
if (!vis[v]) {
q[back++]=v;
vis[v]=;
}
}
}
for (int i=;i<=n2;++i)
if (!vis[i])
return ;
return ;
}
int main(void) {
memset(head,-,sizeof(head));
scanf("%d %d",&n,&m);
while (m--) {
int u=,v=;
scanf("%d %d",&u,&v);
addEdge(u,v);
}
for (int i=;i<=n;++i)
if (!dfn[i])
tarjan(i);
//建缩点以后的反图 就所有入度为0的点bfs
memset(head2,-,sizeof(head2));
build();
int ans=;
for (int i=;i<=n2;++i)
if (!in[i])
if (bfs(i))
ans+=cnt[i];
printf("%d\n",ans);
return ;
}
上个代码在洛谷不过，求大神指点