AtCoder ARC 108 C - Keep Graph Connected (水色, 500 点)

誤読したーーーーー

• 問題へのリンク

問題概要

頂点数 、辺数 の連結な無向グラフが与えられる (多重辺はありうるが、自己ループはない)。各辺には色がついていて、色は 以上 以下の整数値で与えられる。

各頂点に 以上 以下の色を割り振りたい。このとき、「両端点の色のうちのちょうど一方のみが辺の色」であるような辺のみを残して、他の辺をすべて除去したとき、グラフ全体が連結である状態を保つようにしたい。

そのような頂点への色の塗り分け方が存在するかどうかを判定し、存在するならば実例を一つ挙げよ。

制約

• 
• 

考えたこと

最初誤読して、辺の除去はないのかと思っていた。つまり、すべての辺について「両端のうち片方のみが辺の色」となるようにする必要があるのかと思った。そのバージョンを解くのは難しそう。

連結な状態さえ残せればよいとわかって、一気に視界が開けた。単純にこんな感じで OK。

• 頂点を一つ適当に決めて、その色を適当に決める
• 頂点 v を色 c で塗ったとする
• 頂点 v に接続している各辺 e = (v, w) について
  • 頂点 w がすでに色が塗られていたらなにもしない
  • e の色と c が等しいときは、頂点 w を c 以外の色で塗って頂点 w を深さ優先探索する
  • e の色と c が等しくないときは、頂点 w を色 c で塗って頂点 w を深さ優先探索する

つまり、すべてのケースで塗り分け可能となる。計算量は 。

コード

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

using Edge = pair<int,int>;
using Graph = vector<vector<Edge>>;
int N, M;
Graph G;
void rec(int v, int c, vector<int> &res) {
    res[v] = c;
    for (auto e : G[v]) {
        if (res[e.first] != -1) continue;
        if (e.second == c) rec(e.first, (e.second+1)%N, res);
        else rec(e.first, e.second, res);
    }
}

int main() {
    cin >> N >> M;
    G.assign(N, vector<Edge>());
    for (int i = 0; i < M; ++i) {
        int u, v, c;
        cin >> u >> v >> c;
        --u, --v, --c;
        G[u].emplace_back(v, c);
        G[v].emplace_back(u, c);
    }
    vector<int> res(N, -1);
    rec(0, 0, res);
    for (auto v : res) cout << v+1 << endl;
}