受欢迎的牛（强连通分量）

每一头牛的愿望就是变成一头最受欢迎的牛。

现在有 N 头牛，编号从 1 到 N，给你 M 对整数 (A,B)，表示牛 A 认为牛 B 受欢迎。

这种关系是具有传递性的，如果 A 认为 B 受欢迎，B 认为 C 受欢迎，那么牛 A 也认为牛 C 受欢迎。

你的任务是求出有多少头牛被除自己之外的所有牛认为是受欢迎的。

题目链接：AcWing 1174。

也就是在缩点后的出度为 0 的强连通分量中是所有满足题目条件的结点，但是这里要保证出度为 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
#include <iostream>
#include <algorithm>
#include <stack>
#include <cstring>
using namespace std;

const int N = 10010, M = 50010;
int h[N], e[M], ne[M], idx;
int dfn[N], sz[N], low[N], timestamp;
int id[N], dout[N], scc_cnt;
stack<int> stk;
bool instk[N];
int n, m;

void tarjan(int u) {
    stk.push(u);
    instk[u] = true;
    dfn[u] = low[u] = ++timestamp;
    
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (dfn[j] == 0){
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if (instk[j]) {
            low[u] = min(low[u], dfn[j]);
        }
    }
    
    if (dfn[u] == low[u]) {
        int y;
        ++scc_cnt;
        do {
            y = stk.top(); stk.pop();
            instk[y] = false;
            id[y] = scc_cnt;
            sz[scc_cnt]++;
        } while (y != u);
    }
}

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int main() {
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }
    
    for (int i = 1; i <= n; i++)
        if (dfn[i] == 0) tarjan(i);
    
    // 对强连通分量建图 这里只统计了出度
    for (int i = 1; i <= n; i++)
        for (int j = h[i]; ~j; j = ne[j]) {
            int k = e[j];
            int a = id[i], b = id[k];
            if (a != b) dout[a]++;
        }
    
    // 按照拓扑序从后向前遍历所有强连通分量
    int zeros = 0, ans = 0;
    for (int i = 1; i <= scc_cnt; i++)
        if (dout[i] == 0) {
            if (++zeros > 1) {
                ans = 0;
                break;
            }
            ans = sz[i];
        }
    
    cout << ans << endl;
    
    return 0;
}

学校网络（强连通分量）

一些学校连接在一个计算机网络上，学校之间存在软件支援协议，每个学校都有它应支援的学校名单（学校 A 支援学校 B，并不表示学校 B 一定要支援学校 A）。

当某校获得一个新软件时，无论是直接获得还是通过网络获得，该校都应立即将这个软件通过网络传送给它应支援的学校。

因此，一个新软件若想让所有学校都能使用，只需将其提供给一些学校即可。

现在请问最少需要将一个新软件直接提供给多少个学校，才能使软件能够通过网络被传送到所有学校？

最少需要添加几条新的支援关系，使得将一个新软件提供给任何一个学校，其他所有学校就都可以通过网络获得该软件？

题目链接：AcWing 367。

对于 Tarjan 缩点后的 DAG，第一问是入度为 0 的点个数，第二问是添加几条边可以让 DAG 构成强连通分量。

定理：在一个 DAG G=(V,E)G=(V,E) 中，设入度为 00 的点集为 PP，出度为 00 的点集为 QQ，那么最少添加 max⁡{∣P∣,∣Q∣}\max\{ |P|, |Q|\} 条边能使其成为强连通分量。

证明：不妨设 ∣P∣≤∣Q∣|P|\le |Q|，若 ∣P∣>∣Q∣|P|\gt |Q| 则在反向图 GTG^T 中求解边数与原问题等价。现证最少添加 ∣Q∣|Q| 条边使 GG 成为一个强连通分量。

当 ∣P∣=1|P|=1 时，这显然是成立的，需要将所有终点与起点连一条边才能使 GG 成为一个强连通分量。

当 ∣P∣>1|P|>1 时，对起点 p0p_0 和它不能到达的终点 q1q_1 连一条边 (p0,q1)(p_0,q_1)；经过 ∣P∣−1|P|-1 次上述操作构造一个新图 G′G' 使 ∣P′∣=1,∣Q′∣=∣Q∣−(∣P∣−1)|P'|=1, |Q'|=|Q|-(|P|-1)，那么这时转化成第一个情况，加上前面的多次操作，最终需要链的边数就是 ∣Q′∣+(∣P∣−1)=∣Q∣|Q'|+(|P|-1)=|Q|，证毕。

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
#include <iostream>
#include <cstring>
#include <stack>
using namespace std;

const int N = 110, M = 10010;
int n;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp, id[N], dout[N], din[N], scc_cnt;
stack<int> stk;
bool instk[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void tarjan(int u) {
    stk.push(u);
    instk[u] = true;
    low[u] = dfn[u] = ++timestamp;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (!dfn[j]) tarjan(j), low[u] = min(low[u], low[j]);
        else if (instk[j]) low[u] = min(low[u], dfn[j]);
    }
    if (low[u] == dfn[u]) {
        int y;
        ++scc_cnt;
        do {
            y = stk.top(); stk.pop();
            instk[y] = false;
            id[y] = scc_cnt;
        } while (y != u);
    }
}

int main() {
    cin >> n;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i++) {
        int j;
        while (cin >> j, j) {
            add(i, j);
        }
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i]) tarjan(i);
    
    for (int i = 1; i <= n; i++)
        for (int j = h[i]; ~j; j = ne[j]) {
            int k = e[j];
            int a = id[i], b = id[k];
            if (a != b) din[b]++, dout[a]++;
        }
    
    int p = 0, q = 0;
    for (int i = 1; i <= scc_cnt; i++) {
        if (din[i] == 0) p++;
        if (dout[i] == 0) q++;
    }
    
    cout << p << endl;
    if (scc_cnt == 1) cout << 0 << endl;
    else cout << max(p, q) << endl;
    return 0;
}

冗余路径（边双连通分量）

为了从 F 个草场中的一个走到另一个，奶牛们有时不得不路过一些她们讨厌的可怕的树。

奶牛们已经厌倦了被迫走某一条路，所以她们想建一些新路，使每一对草场之间都会至少有两条相互分离的路径，这样她们就有多一些选择。

每对草场之间已经有至少一条路径。

给出所有 R 条双向路的描述，每条路连接了两个不同的草场，请计算最少的新建道路的数量，路径由若干道路首尾相连而成。

两条路径相互分离，是指两条路径没有一条重合的道路。

但是，两条分离的路径上可以有一些相同的草场。

对于同一对草场之间，可能已经有两条不同的道路，你也可以在它们之间再建一条道路，作为另一条不同的道路。

题目链接：AcWing 395。

对于一个边双连通分量，一定存在简单环，也就有条不同的道路，所以本题的问题就是通过边双连通分量缩点后形成的树中，最少添加几条边可以使一个树变成边双连通分量。

结论是 ⌈leaf2⌉\lceil \cfrac{\text{leaf}}{2}\rceil 其中 leaf\text{leaf} 是叶结点的数量：将所有叶结点两两连边，如果是奇数个那么将剩下的那个单独和其它任意点连一条边，就构成了边双连通分量。

值得说明的是，对于一个边的编号与其反向边总符合 (0, 1) (2, 3), (4, 5) 的规律，因此异或 1 就能取到一个边的反向边编号。

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
using namespace std;

const int N = 5010, M = 20010;
int n, m;
int h[N], e[M], ne[M], idx;
int low[N], dfn[N], id[N], d[N], timestamp, dcc_cnt;
bool bridge[M];
stack<int> stk;

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void tarjan(int u, int from) {
    dfn[u] = low[u] = ++timestamp;
    stk.push(u);
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (!dfn[j]) {
            tarjan(j, i);
            low[u] = min(low[u], low[j]);
            if (low[j] > dfn[u])
                bridge[i] = bridge[i^1] = true;
        } else if (i != (from ^ 1))
            low[u] = min(low[u], dfn[j]);
    }
    if (dfn[u] == low[u]) {
        ++dcc_cnt;
        int y;
        do {
            y = stk.top(); stk.pop();
            id[y] = dcc_cnt;
        } while (y != u);
    }
}

int main() {
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    
    // 缩点
    for (int i = 1; i <= n; i++)
        if (!dfn[i]) tarjan(i, -1);
    
    for (int i = 0; i < idx; i++)
        if (bridge[i]) d[id[e[i]]]++;
    
    int leaf = 0;
    for (int i = 1; i <= dcc_cnt; i++)
        if (d[i] == 1) leaf++;
    cout << (leaf+1)/2 << endl;
    return 0;
}

电力（点双连通分量）

给定一个由 n 个点 m 条边构成的无向图，请你求出该图删除一个点之后，连通块最多有多少。

题目链接：AcWing 1183。

每个连通块内的割点删掉后能分出的最大连通块数量为 ss，连通块数量总共为 cntcnt，那么答案就是 s+cnt−1s+cnt-1，因为 cnt−1cnt-1 不包含处理出来 ss 的那个连通块。

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
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 10010, M = 30010;
int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;

int root, s;

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void tarjan(int u, int from) {
    dfn[u] = low[u] = ++timestamp;
    int cnt = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (!dfn[j]) {
            tarjan(j, i);
            // 我一开始漏了这句
            low[u] = min(low[u], low[j]);
            if (low[j] >= dfn[u]) cnt++;
        } else if (i != (from ^ 1)) {
            low[u] = min(low[u], dfn[j]);
        }
    }
    
    if (u != root && cnt > 0) ++cnt;
    s = max(s, cnt);
}

int main() {
    while (cin >> n >> m, n || m) {
        memset(h, -1, sizeof h);
        memset(dfn, 0, sizeof dfn);
        memset(low, 0, sizeof low);
        idx = 0, s = 0, timestamp = 0;
        for (int i = 0; i < m; i++) {
            int a, b;
            cin >> a >> b;
            add(a, b), add(b, a);
        }
        
        int cnt = 0;
        for (root = 0; root < n; root++)
            if (!dfn[root]) tarjan(root, -1), cnt++;
        
        cout << s + cnt - 1 << endl;
    }
    return 0;
}

矿场搭建（待补充）

紫题跳了捏。