洛谷P2341《[HAOI2006]受欢迎的牛》

七月 29, 2019 3248

Tarjan 缩点板子题

题目描述

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

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

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

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

输入格式

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

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

输出格式

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

输入输出样例

输入 #1

1
2
3
4
3 3
1 2
2 1
2 3

输出 #1

1
1

说明/提示

只有 3 号奶牛可以做明星

【数据范围】

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

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

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

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

解析

首先把题目转化一下

显然能成为明星的奶牛们一定是互相喜欢的
那么可以这样想：能成为明星的奶牛们都是在一个强连通分量中的，这样意味着互相喜欢
所以问题转化为了求图中强连通分量大小，这个用 Tarjan 来完成

值得注意的是，把强连通分量缩点之后，所得的图一定是一个DAG（这是一个性质）（实际写代码的时候不需要重新建图）
回到题目，缩完点之后，强连通分量对应的点的出度一定为0，而且有且仅有强连通分量对应的点出度为 0，因为如果强连通分量对应的点出度大于 0，则连出去的边与其他的点连到强连通分量的边就构成了一个环，与上面的性质相矛盾

注意到强连通分量对应的点出度为 0，那么该图合法必须要保证只有一个强连通分量（想一想，为什么）

所以写代码的思路就大体形成了：
Tarjan求强连通分量大小➡️缩点求出度➡️判断强连通分量个数➡️输出0或者强连通分量大小

代码实现

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
//
//  LuoguP2341.cpp
//  Title: [HAOI2006]受欢迎的牛
//  Alternatives: BZOJ1051-LOJ10091
//  Debugging
//
//  Created by HandwerSTD on 2019/7/28.
//  Copyright © 2019 HandwerSTD. All rights reserved.
//

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>

const int MAXN = 10000 + 10;
const int MAXM = 50000 + 10;

std::vector<int> head[MAXN];
int dfn[MAXN], low[MAXN];
bool inStack[MAXN];
int rep[MAXM], ren[MAXM];
// 把输入数据存一下
int sizSC[MAXN], ode[MAXN];
int ftot = 0;
int top, Stack[MAXN];
int col, timestamp, SC[MAXN];
// dfn：dfs的时间戳
// low：在点u的子树能到达的节点中dfn的最小值
// SC：点u属于哪一个强连通分量
// inStack：是否在栈中
// sizSC：该强连通分量的大小
// ode：该“点”的出度

void addEdge(int x, int y) { head[x].push_back(y); }

void Tarjan(int u) {
    low[u] = dfn[u] = ++timestamp;
    Stack[++top] = u;
    inStack[u] = true;
    for (int i = 0, siz = (int) head[u].size(); i < siz; ++i) {
        int v = head[u][i];
        if (!dfn[v]) {
            // 没被访问过
            Tarjan(v);
            low[u] = std::min(low[u], low[v]);
        } else if (inStack[v]) low[u] = std::min(low[u], low[v]);
    }
    if (dfn[u] == low[u]) {
        // 意味着u的子树中没有能到达u的祖先的边，也就是找到了一个强连通分量
        SC[u] = ++col;
        inStack[u] = false;
        ++sizSC[col];
        while (Stack[top] != u) {
            SC[Stack[top]] = col;
            ++sizSC[col];
            inStack[Stack[top--]] = false;
        }
        top--;
    }
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        int a, b;
        scanf("%d %d", &a, &b);
        addEdge(a, b);
    }
    for (int i = 1; i <= n; ++i)
        if (!dfn[i]) Tarjan(i);
    // 对所有联通块进行tarjan
    
    for (int i = 1; i <= n; ++i) {
        for (int j = 0, siz = (int) head[i].size(); j < siz; ++j) {
            int v = head[i][j];
            if (SC[i] != SC[v]) ++ode[SC[i]];
        }
    }
    
    int ans = 0;
    for (int i = 1; i <= col; ++i)
        if (!ode[i]) {
            if (ans) { printf("0"); return 0; }
            ans = sizSC[i];
        }
    printf("%d\n", ans);
    return 0;
}
// tm这题我调了2h