【tarjan】BZOJ 1051:受欢迎的牛

2023-03-10 10:49:46

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

Sample Output

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 ;

 }

码农公寓