AtCoder Grand Contest 014: B - Unplanned Queries
未証明で投げてみたら通った。
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;
}