Luogu2341 - [HAOI2006]受欢迎的牛

2017/10/16

题目

每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶 牛都是自恋狂,每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果A喜 欢B,B喜欢C,那么A也喜欢C。牛栏里共有N 头奶牛,给定一些奶牛之间的爱慕关系,请你 算出有多少头奶牛可以当明星。

N <= 10000, M <= 50000

代码

先 Tarjan 算法求出强连通分量,出度为零的强连通分量大小就是答案,如果有多个出度为零,则无解。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
//#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int SIZ = 100000 + 1007;
int N, M;

namespace pha1 {
    struct tgno {
        int u, v; tgno* n;
    } POOL[SIZ], *Head[SIZ]; int ppos;
    
    void addEdge(int u, int v) {
        POOL[ppos].u = u;
        POOL[ppos].v = v;
        POOL[ppos].n = Head[u];
        Head[u] = &POOL[ppos++];
    }
    
    int T = 0, B = 0;
    int dfn[SIZ], low[SIZ], bel[SIZ], stk[SIZ], spos, instk[SIZ], out[SIZ], siz[SIZ];
    void dfs(int u) {
        dfn[u] = low[u] = ++T;
        stk[++spos] = u; instk[u] = 1;
        
        typedef tgno* It;
        for(It i=Head[u];i;i=i->n) {
            if(!dfn[i->v]) {
                dfs(i->v);
                low[u] = min(low[u], low[i->v]);
            } else if(instk[i->v]) {
                low[u] = min(low[u], dfn[i->v]);
            }
        }
        
        if(dfn[u] == low[u]) {
            int c;
            ++B;
            int sz = 0;
            while((c = stk[spos])) {
                sz++;
                spos--; instk[c] = 0;
                bel[c] = B;
                
                if(c == u) break;
            }
            
            siz[B] = sz;
        }
    }
    
    void Tarjan() {
        for(int i=1;i<=N;i++) {
            if(!dfn[i]) dfs(i);
        }
        
        for(int i=0;i<ppos;i++) {
            if(bel[POOL[i].u] != bel[POOL[i].v]) {
                out[bel[POOL[i].u]]++;
            }
        }
    }
};

int main() {
    scanf("%d %d", &N, &M);
    
    int u, v;
    for(int i=0;i<M;i++) {
        scanf("%d %d", &u, &v);
        
        pha1 :: addEdge(u, v);
    }
    
    pha1 :: Tarjan();
    
//    for(int i=1;i<=N;i++) {
//        printf("%d ", pha1 :: bel[i]);
//    }
//    puts("");
    
    int ans = 0;
    bool flag = false, noans = false;
    for(int i=1;i<=pha1::B;i++) {
        if(!pha1::out[i]) {
            if(flag) noans = true;
            else {
                flag = true;
                ans = pha1::siz[i];
            }
        }
    }
    
    printf("%d\n", noans ? 0 : ans);
}