Codeforces Round #429 Div.2 D / Div.1 B - Leha and another game about graph

http://codeforces.com/contest/840/problem/B

問題概要

N頂点M辺の連結な無向グラフGと、N要素の数列Dが与えられる。数列Dの要素は-1, 0, 1のいずれかである。Gから任意の辺集合を選び、選ばれた辺以外を削除するとき、以下の条件を満たすことができるか判定せよ。またできるのであればそのような辺の集合を構成せよ。

  • D[i]が0なら頂点iの次数は偶数
  • D[i]が1なら頂点iの次数は奇数
  • D[i]が-1なら頂点iの次数はなんでもよい

N, M <= 3 * 105

解法

(次数はすべてmod2で述べる。)

まずグラフの次数の合計は必ず偶数になる(辺1本につき合計次数が2増えるから)ため、Dに-1がなくかつDの合計が奇数の場合は条件は満たせない。

一度全部の辺を削除して、辺を張り直す問題として考えてみる。ここでひとつのパスを選んでそのパスに含まれる辺を張ることにすると、パスの端点のみ次数が1になり、途中の点は0のままになる。このやり方で次数が1の点を2つずつ増やしていくことができる。もしパスを張る過程で以前張ったパスと同じ辺を通ることになったら、単にその辺を消せば次数は保存される。結局この問題は「D[i]=1なる点を2つとってきてそれらをつなぐパスを見つけることをD[i]=1の頂点がなくなるまで繰り返す」問題と同等になる。

しかし一般的な無向グラフ上で愚直にペアを作ってDFSなりBFSでそのパスを見つけ…という操作を行っていると最悪でO(N2)かかる(ペアの数*DFSの計算量)。ここでパスを簡単に構成できる形をしたグラフがあって、それは木である。グラフは連結であることが保証されているため、一部の辺だけ取ってくるとグラフ上で木を作ることができる。この木において「(D[i]+sum(dfs(iの子ども))) mod 2を返す、このとき返り値が0なら親との間の辺を有効にする」というDFSで解が構成できる。-1はつじつま合わせで適当に0か1のどちらかに寄せればいい。

感想

説明難しすぎて自分でも何言ってるかわからないんですが、1の間をパスでつなぐんだっていうのとパスの構成は木にすると簡単っていうのがたぶん勘所じゃないかと思います。

コード (C++)

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);i++)
#define REP2(i,m,n) for (int i=m;i<(n);i++)
typedef long long ll;

int N, M;
int D[300010];
vector<pair<int, int>> edges[300010];
int edge_states[300010];
bool used[300010];

void dfs1(int n) {
    used[n] = true;
    for (auto m: edges[n]) {
        if (used[m.first]) continue;
        edge_states[m.second] = 0;
        dfs1(m.first);
    }
}

int dfs2(int n, int p, int pe) {
    int cnt = D[n] == 1;
    for (auto m: edges[n]) {
        if (edge_states[m.second] == -1 || m.first == p) continue;
        cnt += dfs2(m.first, n, m.second);
    }
    if (cnt % 2 == 1) edge_states[pe] = 1;
    return cnt % 2;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);

    cin >> N >> M;
    REP(i, N) cin >> D[i];
    REP(i, M) {
        int a, b;
        cin >> a >> b;
        edges[a - 1].push_back(make_pair(b - 1, i));
        edges[b - 1].push_back(make_pair(a - 1, i));
    }

    int cnt1 = 0;
    int cnt_1 = 0;
    REP(i, N) if (D[i] == 1) cnt1 += 1; else if (D[i] == -1) cnt_1 += 1;
    if (cnt1 % 2 == 1 && cnt_1 == 0) {
        cout << -1 << endl;
        return 0;
    } else if (cnt1 % 2 == 1 && cnt_1 > 0) {
        REP(i, N) if (D[i] == -1) {D[i] = 1; break;}
    }

    REP(i, M) edge_states[i] = -1;
    memset(used, 0, sizeof(used));

    dfs1(0);
    dfs2(0, -1, 0);

    int ans = 0;
    REP(i, M) if (edge_states[i] == 1) ans += 1;

    if (ans == 0) {
        cout << ans << endl;
        return 0;
    }

    cout << ans << endl;
    REP(i, M) if (edge_states[i] == 1) cout << i + 1 << "\n";
}