Learning Algorithms

アルゴリズムの勉強メモ

Atcoder Regular Contest 041 D. 辺彩色

D - 辺彩色

解法

まず辺に色を塗っていく操作を、逆順から見ていきます。この発想は以下のような問題でも使えます。

B - Splatter Painting

そうすると、一回塗った辺はもう変更することができないという操作に変えることができます。すると、各辺は条件を満たしている色でしか通過できないという条件を作ることができ、$DFS$ で普通に探索できます。

さて、次に交互に塗っていくという性質から、奇閉路を一つでも作れば、そこからすべての辺を塗っていけることに気づきます。逆に奇閉路が作れない場合は、二部グラフなので、順番に関係なく辺を選んでいけます。

すなわち、貪欲に辺を選んでいって、すべての辺を塗るか、奇閉路を検出すれば、$Yes$ で、そうでなければ $No$ です。

スタートする位置と最初の色は全探索します。

実装中のnode_colorは奇閉路を検知するためのもので、辺の色とは無関係です。

実装
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <functional>
using namespace std;

struct edge {
        int to, color;
};

int main() {
        int n, m;
        scanf("%d %d", &n, &m);
        vector<vector<edge>> g(n);
        for (int i = 0; i < m; i ++) {
                int a, b;
                char c;
                scanf("%d %d %c", &a, &b, &c);
                a --, b --;
                int color = (c == 'r' ? 1 : 0);
                g[a].push_back({ b, color });
                g[b].push_back({ a, color });
        }
        for (int i = 0; i < n; i ++) {
                for (int c = 0; c < 2; c ++) {
                        vector<int> node_color(n, -1);
                        set<pair<int, int>> used;
                        function<void (int, int, int)> dfs = [&](int u, int ec, int nc) {
                                node_color[u] = nc;
                                for (auto e : g[u]) {
                                        if (e.color != ec || used.count(make_pair(min(u, e.to), max(u, e.to)))) continue;
                                        used.insert(make_pair(min(u, e.to), max(u, e.to)));
                                        if (node_color[e.to] == -1 || node_color[e.to] == !nc) {
                                                dfs(e.to, !ec, !nc);
                                        } else {
                                                puts("Yes");
                                                exit(0);
                                        }
                                }
                        };
                        dfs(i, c, 0);
                        if (used.size() == m) {
                                puts("Yes");
                                exit(0);
                        }
                }
        }
        puts("No");
        exit(0);
}