[心之碎片][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 的解法没想出来, 做不来就手玩一些数据, 找找规律然后猜一下
当然, 可以给出一种情况大概证一下 (大概率不会


代码

/*
tarjan 缩点, 每个点属于的 scc 做出来
入度出度做出来
ans1 = 缩点后入度0的点数
ans2 = max(起点, 终点)
*/

#include <bits/stdc++.h>
using namespace std;

const int N = 105;

int n;
vector<int> e[N];

int dfn[N], low[N], tot;
int bel[N], scc_cnt, stk[N], top;
bitset<N> instk;

void Tarjan(int u){
    dfn[u] = low[u] = ++tot;
    stk[++top] = u;
    instk[u] = 1;

    for(auto ed : e[u]){
        if(!dfn[ed]){
            Tarjan(ed);
            low[u] = min(low[u], low[ed]);
            continue;
        }
        if(instk[ed]){
            low[u] = min(low[u], dfn[ed]);
        }
    }

    if(dfn[u] == low[u]){
        int v;
        scc_cnt++;
        do{
            v = stk[top--];
            bel[v] = scc_cnt;
            instk[v] = 0;
        } while(u != v);
    }
}

int din[N], dout[N], in, out;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i = 1; i <= n; i++){
        int x;
        while(cin >> x){
            if(!x) break;
            e[i].emplace_back(x);
        }
    }

    for(int i = 1; i <= n; i++){
        if(!dfn[i]) Tarjan(i);
    }

    for(int i = 1; i <= n; i++){
        for(auto ed : e[i]){
            if(bel[i] == bel[ed]) continue;
            din[bel[ed]]++;
            dout[bel[i]]++;
        }
    }

    for(int i = 1; i <= scc_cnt; i++){
        if(!din[i]) in++;
        if(!dout[i]) out++;
    }

    
    cout << in << '\n';
    if(scc_cnt == 1) cout << 0;
    else cout << max(in, out);

    return 0;
}

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的缩点更多，则需要添加至少那么多条边使它们能传递信息出去。

### 代码实现

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

#include <bits/stdc++.h>
using namespace std;

const int N = 105;
vector<int> graph[N], e[N];
int dfn[N], low[N], tot;
int scc_cnt, stk[N], top;
int bel[N]; // 每个点属于的强连通分量编号
bitset<N> instk;
int din[N], dout[N];

void Tarjan(int u) {
    dfn[u] = low[u] = ++tot;
    stk[++top] = u;
    instk[u] = 1;
    
    for (auto v : graph[u]) {
        if (!dfn[v]) {
            Tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (instk[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    
    if (dfn[u] == low[u]) {
        ++scc_cnt;
        int v;
        do {
            v = stk[top--];
            bel[v] = scc_cnt;
            instk[v] = 0;
        } while (u != v);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, x;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        while (cin >> x && x) {
            graph[i].push_back(x);
        }
    }

    // 使用 Tarjan 算法求解所有强连通分量
    for (int i = 1; i <= n; ++i) {
        if (!dfn[i]) {
            Tarjan(i);
        }
    }

    // 缩点并计算新的入度和出度
    for (int u = 1; u <= n; ++u) {
        for (auto v : graph[u]) {
            if (bel[u] != bel[v]) {
                e[bel[u]].push_back(bel[v]);
                din[bel[v]]++;
                dout[bel[u]]++;
            }
        }
    }

    int ans1 = 0, ans2 = 0;
    for (int i = 1; i <= scc_cnt; ++i) {
        if (din[i] == 0) ans1++;
        if (dout[i] == 0) ans2++;
    }
    
    // 如果只有一个强连通分量，则不需要额外添加边
    if (scc_cnt == 1) ans2 = 0;
    
    cout << ans1 << endl;
    cout << max(ans1, ans2) << endl;

    return 0;
}

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

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