柿子饼同学 发表于 2024-6-23 22:04:53

[心之碎片][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;

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

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

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

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

int din, dout, 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.emplace_back(x);
      }
    }

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

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

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

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

    return 0;
}

FishC 发表于 2024-6-23 22:05:19

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

### 问题解读

我们要解决的问题是找出图中的强连通分量，并缩点，然后计算两个值:
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, e;
int dfn, low, tot;
int scc_cnt, stk, top;
int bel; // 每个点属于的强连通分量编号
bitset<N> instk;
int din, dout;

void Tarjan(int u) {
    dfn = low = ++tot;
    stk[++top] = u;
    instk = 1;
   
    for (auto v : graph) {
      if (!dfn) {
            Tarjan(v);
            low = min(low, low);
      } else if (instk) {
            low = min(low, dfn);
      }
    }
   
    if (dfn == low) {
      ++scc_cnt;
      int v;
      do {
            v = stk;
            bel = scc_cnt;
            instk = 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.push_back(x);
      }
    }

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

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

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

    return 0;
}

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

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。
页: [1]
查看完整版本: [心之碎片][0623] - P2746校园网