BZOJ1051 [HAOI2006]受欢迎的牛 强连通分量缩点

关于板子 可参考 wlxy的博客

BZOJ1051 [HAOI2006]受欢迎的牛

[HAOI2006]受欢迎的牛 の 传送门

---

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
1

「数据范围」
10%的数据N<=20, M<=50
30%的数据N<=1000,M<=20000
70%的数据N<=5000,M<=50000
100%的数据N<=10000,M<=50000

---

tarjan强连通分量缩点模板题吧
虽然很久很久以前我写了很久很久TAT
出度为0的点只有一个才有解

---

Code

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

const int N = 10007, M = 50007;
int n, m, cnt, scc, tim, ans, head[N], to[M], nxt[M], low[N], dfn[N], belong[N], vis[N], hav[N], chu[N];
stack <int> S;

inline int read(){
    int ans = 0, f = 1;
    char ch = getchar();
    for(; ch < '0' || ch > '9'; ch = getchar())
        if (ch == '-')
            f = 0;
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        ans = (ans << 3) + (ans << 1) + ch - 48;
    return f? ans: -ans;
}
void add(int u, int v){nxt[++cnt] = head[u]; to[cnt] = v; head[u] = cnt;}
void tarjan(int u){
    dfn[u] = low[u] = ++tim;
    S.push(u);
    vis[u] = 1;
    int v;
    for (int i = head[u]; i; i = nxt[i]){
        v = to[i];
        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]){
        scc++;
        do {
            v = S.top();
            vis[v] = 0;
            belong[v] = scc;
            hav[scc]++;
            S.pop();
        } while(u != v);
    }
}
int main(){
    tim = cnt = scc = 0;
    n = read(), m = read();
    while (S.size())
        S.pop();
    for (register int i = 1; i <= m; ++i){
        int u = read(), v = read();
        add(u, v);
    }
    for (register int i = 1; i <= n; ++i)
        if (!dfn[i]) tarjan(i);
    for (register int k = 1; k <= n; ++k)
        for (int i = head[k]; i; i = nxt[i]){
            int v = to[i];
            if (belong[k] != belong[v])
                chu[belong[k]]++;
        }    
    ans = 0;
    for (int i = 1; i <= scc; ++i){
        if (!chu[i])
            if (ans){
                printf("0
");
                return 0;
            }
            else
                ans = hav[i];
    }
    printf("%d
", ans);
    return 0;
}