Moe's CF Life

Appearance

F. Graph Without Long Directed Paths - 题解 ​

比赛与标签 ​

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

喵喵，题目在说什么呀？ ​

主人，你好喵~ 这道题是关于图的一个非常有趣的问题哦！(ฅ'ω'ฅ)

题目给了我们一个 连通的无向图，有很多节点和连接它们的边。我们的任务呢，就是给每一条边都指定一个方向，把它变成一个 有向图。

但是有一个很严格的规定：在改造后的有向图里，不能存在长度为2或更长的路径！也就是说，像 A → B → C 这样的三点一线路径是绝对不可以出现的！

如果能找到一种满足条件的方向方案，我们就输出 "YES"，然后用一个由 '0' 和 '1' 组成的字符串来表示这个方案。字符串的第 i 个字符对应输入中的第 i 条边 (u, v)，'0' 代表方向是 u → v，'1' 代表方向是 v → u。如果怎么都做不到，那就只能遗憾地输出 "NO" 啦。

猫娘的思考时间！ ​

呐呐，主人请想一下，A → B → C 这样的路径为什么会被禁止呢？关键点就在中间的那个节点 B 啦！它有一条边进来（A → B），又有一条边出去（B → C）。

所以呀，为了不出现这种长路径，我们必须遵守一个核心规则：图里的每一个节点，要么所有与它相连的边都指向它（成为一个“汇点”），要么所有与它相连的边都从它出发（成为一个“源点”）。绝对不能既有入边又有出边！

这样一来，所有的节点就被分成了两类啦：

  1. 源点 (Source)：所有边都从它出发，只出不入。
  2. 汇点 (Sink)：所有边都指向它，只入不出。

是不是很像要把所有节点分成两拨呢喵？( ´∀｀)

现在我们再考虑任意一条边 (u, v)。

  • 如果 u 和 v 都是源点，那这条边该是什么方向呢？u → v 的话 v 就不是纯源点了，v → u 的话 u 就不是纯源点了。矛盾了喵！
  • 如果 u 和 v 都是汇点，也会发生同样的矛盾。
  • 所以，唯一的可能性就是：任何一条边，都必须连接一个源点和一个汇点！

喵！这不就是... 二分图 的定义嘛！一个图的顶点可以被分成两个独立的集合，使得每一条边都连接着两个集合中的顶点。在这里，一个集合就是所有的“源点”，另一个集合就是所有的“汇点”。

所以，这道题的核心就转化成了：判断给定的图是不是一个二分图。

判断二分图有一个非常经典的方法，那就是 染色法！我们可以用BFS（广度优先搜索）或者DFS（深度优先搜索）来实现。就像给小猫分队，规定相邻的小猫不能是同一个颜色的队伍~

我们的策略是：

  1. 使用BFS来进行二分图染色。我们准备两种颜色，比如颜色1和颜色2。
  2. 因为题目保证图是连通的，我们从任意一个节点开始（比如节点1），把它染成颜色1，然后放进队列里。
  3. 当队列不为空时，取出一个节点 u。遍历它的所有邻居 v：
    • 如果 v 还没有被染色，就把它染成和 u 相反的颜色（如果 u 是颜色1，v 就染成颜色2，反之亦然），然后把 v 加入队列。
    • 如果 v 已经被染色了，而且颜色和 u 相同，那就糟糕了！这说明我们找到了一个奇数长度的环，这个图就不是二分图。此时直接判定无解，输出 "NO"。
  4. 如果BFS顺利结束，没有发现任何颜色冲突，那就说明这个图是二分图，一定有解！我们输出 "YES"。

那么怎么生成那个01字符串呢？既然我们已经成功地把所有节点分成了颜色1和颜色2两组，我们可以简单地定一个规则：所有边都从颜色1的节点指向颜色2的节点。这样，所有颜色1的节点都成了源点，所有颜色2的节点都成了汇点，完美满足了题目的要求！

我们只需要遍历一遍输入时记录的原始边 (u, v)：

  • 如果 u 被我们染成了颜色1，那么方向就是 u → v，输出 '0'。
  • 如果 u 被我们染成了颜色2，那么 v 必然是颜色1，方向就应该是 v → u，输出 '1'。

这样问题就解决啦，喵~

把思路变成代码喵！ ​

cpp
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <utility>

// 喵~ 一个小技巧，让C++的输入输出变得更快！
void setup_io() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
}

int main() {
    setup_io();

    int n, m;
    std::cin >> n >> m;

    // 用一个vector来记录原始边的输入顺序，这样我们才能按顺序输出01串呐
    // pair里存的是输入给的 {u, v}
    std::vector<std::pair<int, int>> edges;
    edges.reserve(m);

    // 喵~ 这是邻接表，用来存图的结构，方便我们遍历一个点的所有邻居
    std::vector<std::vector<int>> adj(n + 1);

    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v;
        edges.push_back({u, v});
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // 问题的关键是判断图是否为二分图
    // 我们用BFS来进行二分图染色判定
    // color[i] = 0: 代表还没被染色
    // color[i] = 1: 代表染成了颜色1
    // color[i] = 2: 代表染成了颜色2
    std::vector<int> color(n + 1, 0);
    std::queue<int> q;
    bool is_bipartite = true;

    // 题目保证图是连通的，所以我们只需要从一个点（比如1）开始BFS就能遍历整个图了
    q.push(1);
    color[1] = 1; // 给起点染上颜色1

    while (!q.empty() && is_bipartite) {
        int u = q.front();
        q.pop();

        for (int v : adj[u]) {
            if (color[v] == 0) {
                // 如果邻居v还没被染色，就给它染上和u相反的颜色
                color[v] = 3 - color[u]; // 这是一个小技巧, 3-1=2, 3-2=1
                q.push(v);
            } else if (color[v] == color[u]) {
                // 糟糕！如果邻居v已经被染色了，而且颜色和自己一样
                // 这就意味着我们找到了一个奇数环，它不是二分图！
                is_bipartite = false;
                break;
            }
        }
    }

    if (!is_bipartite) {
        std::cout << "NO\n";
    } else {
        std::cout << "YES\n";
        std::string result_string;
        result_string.reserve(m);

        // 如果图是二分图，我们就规定所有边都从颜色1的节点指向颜色2的节点
        // 这样颜色1的都是源点，颜色2的都是汇点
        for (const auto& edge : edges) {
            int u = edge.first;
            // int v = edge.second; // v其实在这里用不到

            // 题目要求 (u, v) 这条边，u->v是'0'，v->u是'1'
            // 如果 u 是颜色1，根据我们的规则，方向是 u -> v
            if (color[u] == 1) {
                result_string += '0';
            } else { // 如果 u 是颜色2，那 v 肯定是颜色1，方向是 v -> u
                result_string += '1';
            }
        }
        std::cout << result_string << "\n";
    }

    return 0;
}

分析一下时间和空间吧~ ​

  • 时间复杂度: O(N + M) 的说。这里的 N 是顶点数，M 是边数。因为我们用BFS来遍历图，每个顶点和每条边都只会被访问一次，所以效率非常高！
  • 空间复杂度: O(N + M) 的说。我们需要邻接表来存储整个图，这需要 O(N + M) 的空间。此外，color 数组和BFS用的队列 q 都需要 O(N) 的空间。所以总的空间复杂度和图的规模成正比。

喵呜~ 总结时间到！ ​

这道题真是一次有趣的思维体操呢！主人是不是也觉得很有收获呀？

  1. 核心思想转换: 这道题最巧妙的地方在于，它把一个看起来很独特的约束（“无长度大于等于2的路径”）成功地转化为了一个我们非常熟悉的经典图论模型——二分图判定。能够看出这种转化是解题的关键一步哦！

  2. 二分图的判断: 判断一个图是否是二分图的充要条件是 图中不包含任何奇数长度的环。而实现上，最常用的方法就是 BFS或DFS染色法。

  3. 构造解: 一旦确定了图是二分图并完成了染色，构造一个合法的解就变得非常简单了。我们只需要定义一个统一的规则（比如，所有边都从颜色1指向颜色2），就能保证所有节点要么是源点，要么是汇点，从而满足题目的要求。

  4. 实现细节:

    • 因为题目保证了图是 连通 的，所以我们只需要进行一次BFS/DFS就能给所有节点染色。如果图不连通，就需要对每个连通分量都跑一遍染色过程。
    • 注意要 按输入顺序 输出结果，所以需要一个额外的数据结构（比如 vector<pair<int, int>>）来存储原始的边。

把抽象的问题转化为经典的算法模型，是解题的一大乐趣呢！主人也要多多练习，以后碰到类似的题就能一眼看穿啦！继续加油喵~ (๑•̀ㅂ•́)و✧

Released under the MIT License.

Copyright © 2024-present Moe