洛谷P2341 [HAOI2006] 受欢迎的牛

题目描述

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

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

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

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

输入输出格式

输入格式：

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

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

输出格式：

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

输入输出样例

输入样例#1：

输出样例#1：

说明

只有 3 号奶牛可以做明星

【数据范围】

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

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

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

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

　　最近经常水这些蓝题雾】

提供一个思路就完事了：Tarjan的思路

　　如果这个分量中的任意一个点被仰慕，那么说明这个分量中的所有的牛都会被仰慕，那么我们就把这个图全部缩成强连通分量，这个图就变成有向无环图。

　　这时我们会发现，被所有牛仰慕的牛出度一定是为0的，因为是有向无环图，如果被所有牛仰慕，自己又仰慕别人，那么就会产生一个环。

　　因为我们只关注一个分量的出度是否为0，所以不用判断两个分量间的边是否重复统计

　　其次，如果这个图存在一个以上出度为0的强连通分量，这个图就会变成非连通图，就不存在被所有牛仰慕的牛，直接输出0就OK啦。

放上代码。

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<stack>
using namespace std;

const int MA=1e4+5;
int n,m,sum,ans;
int head[MA],ecnt;
int low[MA],dfn[MA],ti;
int col[MA],cnt[MA],du[MA];
bool vis[MA];
struct ss{
    int self,to,nxt;
}t[MA*10];
stack<int> s; 

inline void add(int a,int b) {
    t[++ecnt].self=a;
    t[ecnt].nxt=head[a];
    t[ecnt].to=b;
    head[a]=ecnt;
    return;
}

inline int read() {
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); 
    return x;
}

void Tar(int x) {
    dfn[x]=low[x]=++ti;
    vis[x]=1;
    s.push(x); 
    for(int i=head[x];i;i=t[i].nxt) {
        int y=t[i].to;
        if(!dfn[y]) {
            Tar(y);
            low[x]=min(low[x],low[y]);
        }
        else if(vis[y]) low[x]=min(low[x],dfn[y]);
    }
    int sl;
    if(dfn[x]==low[x]) {
        ++ecnt;
        do{
            sl=s.top();
            s.pop();
            vis[sl]=0;
            col[sl]=ecnt;
            cnt[ecnt]++;
        }while(sl!=x); 
    }
}

int main()
{
    n=read();
    m=read();
    for(int i=1;i<=m;i++) {
        int a=read();
        int b=read();
        add(a,b);
    }
    ecnt=0;
    for(int i=1;i<=n;i++) 
        if(!dfn[i]) Tar(i);
    for(int k=1;k<=n;k++)
        for(int i=head[k];i;i=t[i].nxt) {
            int u=t[i].to;
            if(col[k]!=col[u]) {
                du[col[k]]++;
            }
        }
    int nw=0;
    for(int i=1;i<=ecnt;i++)
        if(!du[i]) {
            if(nw) {
                printf("0
");
                return 0;
            }
        nw=i;
    }
    printf("%d
",cnt[nw]);
    return 0;
}

　　完成！

谢谢