「POI 2008」CLO

题目大意：给定一个无向图，问能否每个点匹配一条边。

类似于「SCOI 2010 连续攻击游戏」的做法。

#include <cstdio>
 
int n, m, fa[100005], ok[100005];
 
void swap(int &x, int &y) {
    x ^= y, y ^= x, x ^= y;
}
int find(int x) {
    if (x != fa[x]) fa[x] = find(fa[x]);
    return fa[x];
}
 
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) fa[i] = i;
    for (int i = 1; i <= m; ++i) {
        int x, y; scanf("%d%d", &x, &y);
        int fx = find(x), fy = find(y);
        if (fx == fy) ok[fx] = 1;
        else ok[fx] = ok[fx] | ok[fy], fa[fy] = fx;
    }
    for (int i = 1; i <= n; ++i)
        if (fa[i] == i && !ok[i]) { puts("NIE"); return 0; }
    puts("TAK");
    return 0;
}