[心之碎片][0623] - P2746校园网

柿子饼同学

P2476


知识点
tarjan强连通分量


思路
求出所有强连通分量, 缩点
ans1 = 入度为 0 点的总数
因为显然, 入度为 0 点没法接受到软件
ans2 = 0(scc == 1) 或 max(入度0, 出度0)
想象一条条从起点到终点的有向边, 我们的目标是把这个图变成一整个强连通图
从终点到起点连一条边, 我们就减少了一对终点和起点, 所以连接 max(入度0, 出度0) 条边就能让整个变成 scc
https://www.luogu.com.cn/article/4hmcb1h5


需要进步的地方
ans2 的解法没想出来, 做不来就手玩一些数据, 找找规律然后猜一下
当然, 可以给出一种情况大概证一下 (大概率不会


代码

1. /*
   
2. tarjan 缩点, 每个点属于的 scc 做出来
   
3. 入度出度做出来
   
4. ans1 = 缩点后入度0的点数
   
5. ans2 = max(起点, 终点)
   
6. */
   
7. 
   
8. #include <bits/stdc++.h>
   
9. using namespace std;
   
10. 
    
11. const int N = 105;
    
12. 
    
13. int n;
    
14. vector<int> e[N];
    
15. 
    
16. int dfn[N], low[N], tot;
    
17. int bel[N], scc_cnt, stk[N], top;
    
18. bitset<N> instk;
    
19. 
    
20. void Tarjan(int u){
    
21.     dfn[u] = low[u] = ++tot;
    
22.     stk[++top] = u;
    
23.     instk[u] = 1;
    
24. 
    
25.     for(auto ed : e[u]){
    
26.         if(!dfn[ed]){
    
27.             Tarjan(ed);
    
28.             low[u] = min(low[u], low[ed]);
    
29.             continue;
    
30.         }
    
31.         if(instk[ed]){
    
32.             low[u] = min(low[u], dfn[ed]);
    
33.         }
    
34.     }
    
35. 
    
36.     if(dfn[u] == low[u]){
    
37.         int v;
    
38.         scc_cnt++;
    
39.         do{
    
40.             v = stk[top--];
    
41.             bel[v] = scc_cnt;
    
42.             instk[v] = 0;
    
43.         } while(u != v);
    
44.     }
    
45. }
    
46. 
    
47. int din[N], dout[N], in, out;
    
48. 
    
49. int main(){
    
50.     ios::sync_with_stdio(0);
    
51.     cin.tie(0);
    
52. 
    
53.     cin >> n;
    
54.     for(int i = 1; i <= n; i++){
    
55.         int x;
    
56.         while(cin >> x){
    
57.             if(!x) break;
    
58.             e[i].emplace_back(x);
    
59.         }
    
60.     }
    
61. 
    
62.     for(int i = 1; i <= n; i++){
    
63.         if(!dfn[i]) Tarjan(i);
    
64.     }
    
65. 
    
66.     for(int i = 1; i <= n; i++){
    
67.         for(auto ed : e[i]){
    
68.             if(bel[i] == bel[ed]) continue;
    
69.             din[bel[ed]]++;
    
70.             dout[bel[i]]++;
    
71.         }
    
72.     }
    
73. 
    
74.     for(int i = 1; i <= scc_cnt; i++){
    
75.         if(!din[i]) in++;
    
76.         if(!dout[i]) out++;
    
77.     }
    
78. 
    
79.    
    
80.     cout << in << '\n';
    
81.     if(scc_cnt == 1) cout << 0;
    
82.     else cout << max(in, out);
    
83. 
    
84.     return 0;
    
85. }

复制代码

FishC

哈哈，好家伙，看到你这段代码和问题描述，我觉得我得拿出传说中的通俗易懂且幽默的解答方式来帮你解惑了。让我们先来拆解一下题目吧。

### 问题解读

我们要解决的问题是找出图中的强连通分量，并缩点，然后计算两个值:
1. `ans1`: 缩点后入度为 0 的顶点数
2. `ans2`: 一些奇妙的东西，与入度和出度有关，我们稍后细说。

### 强连通分量和缩点

首先，什么是强连通分量（SCC，Strongly Connected Component）呢？简单粗暴地说，如果一个有向图中的某个子图，它里面的任意两个点之间都可以互相到达，那么这些点就组成一个强连通分量。

### Tarjan算法

Tarjan算法是一种非常高效的求解强连通分量的算法，具体原理这里不展开细讲，总之，它通过DFS（深度优先搜索）和一些巧妙的数据结构，可以在线性时间内把这些强连通分量给搞出来。

### 缩点

缩点的意思是把每个强连通分量看作一个大点，这样我们的图就变成一个缩点后的图了。在这个缩点图里，每个点实际上是若干个原图中的点的集合，缩点图里的边代表原图中那些跨越了不同强连通分量的边。

### 求解过程

1. 用 Tarjan 算法找到所有的强连通分量，并标记每个节点所属的SCC。
2. 构建缩点后的新图，并计算各个缩点的入度和出度。
3. `ans1` 就是新图中入度为0的点的数量。
4. `ans2` 需要稍微多琢磨一下，我们的目标是尽可能少地添加边，使得整个图变成一个强连通图。通过分析可以发现，答案其实就是 `max(入度为0的缩点数, 出度为0的缩点数)`。
    - 因为如果入度为0的缩点更多，则需要添加至少那么多条边使它们接收到信息。
    - 同理，如果出度为0的缩点更多，则需要添加至少那么多条边使它们能传递信息出去。

### 代码实现

好啦，理论部分完事儿，咱们开始翻译成代码吧。我会稍微修改你的代码，使之更完整和清晰：

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. const int N = 105;
   
5. vector<int> graph[N], e[N];
   
6. int dfn[N], low[N], tot;
   
7. int scc_cnt, stk[N], top;
   
8. int bel[N]; // 每个点属于的强连通分量编号
   
9. bitset<N> instk;
   
10. int din[N], dout[N];
    
11. 
    
12. void Tarjan(int u) {
    
13.     dfn[u] = low[u] = ++tot;
    
14.     stk[++top] = u;
    
15.     instk[u] = 1;
    
16.    
    
17.     for (auto v : graph[u]) {
    
18.         if (!dfn[v]) {
    
19.             Tarjan(v);
    
20.             low[u] = min(low[u], low[v]);
    
21.         } else if (instk[v]) {
    
22.             low[u] = min(low[u], dfn[v]);
    
23.         }
    
24.     }
    
25.    
    
26.     if (dfn[u] == low[u]) {
    
27.         ++scc_cnt;
    
28.         int v;
    
29.         do {
    
30.             v = stk[top--];
    
31.             bel[v] = scc_cnt;
    
32.             instk[v] = 0;
    
33.         } while (u != v);
    
34.     }
    
35. }
    
36. 
    
37. int main() {
    
38.     ios::sync_with_stdio(false);
    
39.     cin.tie(0);
    
40. 
    
41.     int n, x;
    
42.     cin >> n;
    
43.     for (int i = 1; i <= n; ++i) {
    
44.         while (cin >> x && x) {
    
45.             graph[i].push_back(x);
    
46.         }
    
47.     }
    
48. 
    
49.     // 使用 Tarjan 算法求解所有强连通分量
    
50.     for (int i = 1; i <= n; ++i) {
    
51.         if (!dfn[i]) {
    
52.             Tarjan(i);
    
53.         }
    
54.     }
    
55. 
    
56.     // 缩点并计算新的入度和出度
    
57.     for (int u = 1; u <= n; ++u) {
    
58.         for (auto v : graph[u]) {
    
59.             if (bel[u] != bel[v]) {
    
60.                 e[bel[u]].push_back(bel[v]);
    
61.                 din[bel[v]]++;
    
62.                 dout[bel[u]]++;
    
63.             }
    
64.         }
    
65.     }
    
66. 
    
67.     int ans1 = 0, ans2 = 0;
    
68.     for (int i = 1; i <= scc_cnt; ++i) {
    
69.         if (din[i] == 0) ans1++;
    
70.         if (dout[i] == 0) ans2++;
    
71.     }
    
72.    
    
73.     // 如果只有一个强连通分量，则不需要额外添加边
    
74.     if (scc_cnt == 1) ans2 = 0;
    
75.    
    
76.     cout << ans1 << endl;
    
77.     cout << max(ans1, ans2) << endl;
    
78. 
    
79.     return 0;
    
80. }

复制代码

希望这些解释和代码对你有所帮助！强连通分量和缩点虽然看上去有点复杂，但通过一步步拆解和实现，其实也并没有那么难。加油哦！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。