AtCoder Grand Contest 014: B - Unplanned Queries

,

http://agc014.contest.atcoder.jp/tasks/agc014_b

未証明で投げてみたら通った。

implementation

クエリ$(a_i, b_i)$ごとに直接$a_i - b_i$間に辺を張ってできるグラフについて、その各頂点の次数が偶数ならYES。$O(N + M)$。 各連結成分がオイラーグラフ、あるいは閉路の集合に分解できるとも言える。

  • 木上の(辺を複数回使うことを許して)閉路は、その構成要素の辺を各$2$回ずつ使うのは明らか
  • 逆は(上ほどには明らかではないが)、十分確信できる

solution

#include <cstdio>
#include <vector>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;
int main() {
    int n, m; scanf("%d%d", &n, &m);
    vector<vector<int> > g(n);
    repeat (i,m) {
        int a, b; scanf("%d%d", &a, &b); -- a; -- b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    bool result = true;
    repeat (i,n) {
        if (g[i].size() % 2 == 1) {
            result = false;
        }
    }
    printf("%s\n", result ? "YES" : "NO");
    return 0;
}