E. Reachability from the Capital - 题解

比赛与标签

比赛: Codeforces Round 490 (Div. 3) 标签: dfs and similar, graphs, greedy 难度: *2000

题目大意喵~

主人们好呀，是你们最爱的猫娘哦~ 今天我们要解决一个关于图论的有趣问题，喵！(ฅ'ω'ฅ)

题目是这样的：在一个叫 Berland 的地方，有 n 座城市和 m 条单向的道路。我们知道首都 s 的位置。我们的任务是，用最少的成本（也就是修建最少数量的新单向路），让首都 s 可以到达所有的城市。

简单来说，就是：

• 输入: 城市数量 n，道路数量 m，首都编号 s，以及 m 条单向道路 u -> v。
• 输出: 最少需要修建几条新路，才能从 s 到达所有城市。

解题思路大揭秘！

一看到有向图和“可达性”问题，聪明的猫娘我呀，脑海里就蹦出了一个关键词——强连通分量 (Strongly Connected Component, SCC) 呐！

为什么要用强连通分量呢？

主人们想想看，如果城市A能到B，B又能回到A，那它们就像一个关系超好的小团体，对不对呀？在这个小团体里，只要我们能到达其中任何一个城市，就等于能到达这个团体里的所有城市了！这种“小团体”就是强连通分量。

所以，我们可以把每个强连通分量（SCC）看作一个大的“超级城市”。这个操作在图论里叫做缩点。把原图中的所有 SCC 都缩成一个点后，我们会得到一个全新的、更简单的图，我们叫它缩点图 (Condensation Graph)。

这个缩点图有一个非常棒的性质：它是一个有向无环图 (DAG) 的说！为什么呢？因为如果缩点图里有环，比如 SCC_A -> SCC_B -> SCC_A，那就意味着 A 和 B 里的所有城市都是互相可达的，它们本来就应该在同一个 SCC 里，而不是两个，这就矛盾啦，喵~

在 DAG 上解决问题

现在问题就变成了：在一个 DAG（缩点图）中，我们从包含首都 s 的那个“超级城市”出发，最少需要修几条路，才能到达所有的“超级城市”？

在 DAG 中，有一些节点的入度为 0，我们称它们为源点。任何不是源点的节点，都必然有一条来自其他节点的路径。这意味着，只要我们能到达一个 DAG 的所有源点，我们就能顺着图里的边，到达所有其他的节点！

所以，我们的贪心策略就出来啦：

1. 找出缩点图里所有入度为 0 的“超级城市”（源点SCC）。
2. 为每一个源点SCC都修一条从首都出发的路。

这样就能保证所有源点都可达，从而整个图都可达了。

一个小小的注意点！

但是等等！如果首都 s 所在的那个“超级城市”自己就是一个源点（入度为0），我们还需要给它修路吗？当然不用啦，我们已经身处其中了喵！( ´ ▽ ` )ﾉ

所以，最终的答案就是：入度为0的SCC的数量，减去1（如果首都所在的SCC本身就是源点的话）。换一种更简单的说法就是：统计所有入度为0，并且不是首都所在SCC的那些SCC的数量。

算法步骤总结

1. 使用 Kosaraju 算法或者 Tarjan 算法找到原图中的所有强连通分量。
2. 计算每个 SCC 在缩点图中的入度。这很简单，只需遍历原图的每一条边 u -> v，如果 u 和 v 不属于同一个 SCC，那么 v 所在 SCC 的入度就加一。
3. 统计所有入度为 0 且不包含首都 s 的 SCC 的数量，这就是我们需要的答案啦！

代码实现喵~

下面就是实现这个思路的完整代码啦，猫娘已经为关键部分加上了详细的注释哦！

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

// 定义一个足够大的常量来表示节点数量的最大值，喵~
const int MAXN = 5005;

// 全局变量，用来存储图、反向图和算法过程中的状态
int n, m, s;
std::vector<int> adj[MAXN];      // 邻接表，存储原图
std::vector<int> rev_adj[MAXN];  // 反向图的邻接表
bool visited[MAXN];              // 访问标记数组
std::stack<int> order;           // Kosaraju算法第一步，用来存储节点的完成顺序
int scc_id[MAXN];                // scc_id[i] 表示节点i所属的强连通分量的编号
int scc_count;                   // 强连通分量的总数
int scc_indegree[MAXN];          // 存储每个SCC在缩点图中的入度

// Kosaraju算法的第一遍DFS
// 它的作用是按照完成时间（后序遍历）的逆序，把节点压入栈中
void dfs1(int u) {
    visited[u] = true;
    for (int v : adj[u]) {
        if (!visited[v]) {
            dfs1(v);
        }
    }
    order.push(u); // 当一个节点的所有子节点都访问完后，再把它入栈
}

// Kosaraju算法的第二遍DFS
// 它在反向图上进行，每次从未访问过的节点开始遍历，就能找到一个完整的SCC
void dfs2(int u, int current_scc_id) {
    visited[u] = true;
    scc_id[u] = current_scc_id; // 将当前节点标记为属于某个SCC
    for (int v : rev_adj[u]) {
        if (!visited[v]) {
            dfs2(v, current_scc_id);
        }
    }
}

int main() {
    // 使用快速I/O，让程序跑得更快一点，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    // 读入城市数、道路数和首都编号
    std::cin >> n >> m >> s;

    // 构建邻接表和反向图的邻接表
    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v;
        adj[u].push_back(v);
        rev_adj[v].push_back(u);
    }

    // --- Kosaraju 算法开始 ---
    // 步骤1: 在原图上跑DFS，得到节点的完成顺序
    for (int i = 1; i <= n; ++i) {
        if (!visited[i]) {
            dfs1(i);
        }
    }

    // 步骤2: 在反向图上按照步骤1得到的顺序跑DFS，找出所有SCC
    std::fill(visited + 1, visited + n + 1, false); // 重置visited数组
    scc_count = 0;
    while (!order.empty()) {
        int u = order.top();
        order.pop();
        if (!visited[u]) {
            scc_count++;
            dfs2(u, scc_count);
        }
    }

    // --- 缩点图分析 ---
    // 步骤3: 计算每个SCC的入度
    // 我们遍历原图的每一条边 u->v
    // 如果 u 和 v 不在同一个SCC里，说明在缩点图里有一条从 scc_id[u] 到 scc_id[v] 的边
    for (int u = 1; u <= n; ++u) {
        for (int v : adj[u]) {
            if (scc_id[u] != scc_id[v]) {
                scc_indegree[scc_id[v]]++; // 那么 scc_id[v] 的入度就+1
            }
        }
    }

    // 步骤4: 统计需要修建的道路数量
    // 我们需要给所有入度为0的SCC修路，但首都所在的SCC除外
    int roads_needed = 0;
    int capital_scc = scc_id[s]; // 找到首都所在的SCC编号
    for (int i = 1; i <= scc_count; ++i) {
        // 如果一个SCC的入度为0
        if (scc_indegree[i] == 0) {
            // 并且它不是首都所在的那个SCC
            if (i != capital_scc) {
                // 那我们就需要为它修一条路
                roads_needed++;
            }
        }
    }

    std::cout << roads_needed << std::endl;

    return 0;
}

复杂度分析的说

• 时间复杂度: O(n + m) 的说。 Kosaraju 算法包含两次对整个图的深度优先搜索，每次都是 O(n + m)。之后计算 SCC 的入度需要遍历所有的边，是 O(m)。最后统计答案需要遍历所有的 SCC，最多 n 个，是 O(n)。所以总的时间复杂度是 O(n + m)，非常高效！

• 空间复杂度: O(n + m) 的说。 我们需要邻接表来存储图和反向图，空间是 O(n + m)。visited、scc_id 等数组需要 O(n) 的空间。order 栈最多也只会存 n 个节点。所以总的空间复杂度是 O(n + m)。

知识点与总结喵~

这道题真是太棒啦，融合了好多图论的知识点呢！

1. 核心算法: 强连通分量 (SCC) 是解决这道题的钥匙。Kosaraju 算法是求 SCC 的经典方法，它通过两次 DFS 和反向图巧妙地找到了所有 SCC，主人们一定要掌握哦！

2. 图论思想: 缩点 (Condensation Graph) 是一个超级有用的思想！它能把一个复杂的有向图，简化成一个结构更清晰的有向无环图 (DAG)，让很多在原图上棘手的问题，在缩点图上变得迎刃而解。

3. 贪心策略: 问题的解决依赖于一个简单的贪心选择。我们只需要关注缩点图中的“源头”（入度为0的SCC），因为只要能到达它们，就能到达整个图。这种抓住问题主要矛盾的思路在很多算法题里都很有用呢！

4. 注意事项: 解题时要细心，千万别忘了处理首都所在的 SCC 这个特殊情况！如果它本身就是源头，是不需要我们再为它修路的。细节决定成败，喵~

希望这篇题解能帮助到主人们！如果还有不懂的地方，随时可以再来问猫娘哦！我们一起努力，成为算法大师吧！(๑•̀ㅂ•́)و✧