[HAOI2006]受欢迎的牛

[HAOI2006]受欢迎的牛

题目描述：

众所周知，喜欢是可以传递的（bushi，给你N头牛，给你M对喜欢关系，如果A喜欢B，B喜欢C，则我们认为A也喜欢C，现在需要求有多少头牛被所有牛喜欢

思路：

还是先进行tarjan缩点，当且仅当存在一个出度为0的点集，则输出该点集的数量，否则输出0

为什么呢？缩点以后得到的个有向无环图，如果一个点出度不为0，则他必然是一条路径的中间位置，也就是他指向下一个点，而因为是无环，则下一个点是不会指向他的，所以他已经不符合所有人都喜欢他的条件了，再说为什么必须只有一个，因为如果存在多个，这些点的出度都为0，那这些点都没法到达别的点，这样就不会存在一个点会被所有人喜欢

此时悟出了人生哲理，当你表现出不想讨好任何人的时候，别人都会来讨好你（bushi

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define eps 1.0E-8
#define endl '\n'
//#define inf 0x3f3f3f3f
#define MAX  300000 + 50
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define max(a,b) (((a)>(b)) ? (a):(b))
#define min(a,b) (((a)>(b)) ? (b):(a))
typedef  long long ll ;
typedef unsigned long long ull;
//不开longlong见祖宗!不看范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int n, m, x, y;

int tot;
int head[MAX];
struct ran{
    int to, nex;
}tr[MAX];
void add(int u, int v){
    tr[++tot].to = v;
    tr[tot].nex = head[u];
    head[u] = tot;
}

int tim;
int cnt;
int color[MAX];
int out[MAX];
int num[MAX];
stack<int>st;
int dfn[MAX], low[MAX];
bool vis[MAX];
void tarjan(int u){
    st.push(u);
    dfn[u] = low[u] = ++tim;
    vis[u] = 1;
    for(int i = head[u]; i; i = tr[i].nex){
        int v = tr[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if(vis[v])low[u] = min(low[u], dfn[v]);
    }
    if(dfn[u] == low[u]){
        int now;
        ++cnt;
        do {
            now = st.top();
            vis[now] = 0;
            st.pop();
            color[now] = cnt;
            ++num[cnt];
        } while (now != u);
    }
}


int main(){
    sdd(n, m);
    for(int i = 1; i <= m; ++i){
        sdd(x, y);
        add(x, y);
    }
    for(int i = 1; i <= n; ++i){
        if(!dfn[i])tarjan(i);
    }
    for(int i = 1; i <= n; ++i){
        for(int j = head[i]; j; j = tr[j].nex){
            int v = tr[j].to;
            if(color[i] != color[v]){
                ++out[color[i]];
            }
        }
    }

    int ans = 0;
    for(int i = 1; i <= cnt; ++i){
        if(!out[i])++ans;
    }
    if(ans == 1){
        for(int i = 1; i <= cnt; ++i){
            if(!out[i]){
                cout << num[i] << endl;
                break;
            }
        }
    }
    else cout << 0 << endl;
    return 0;
}