bzoj1116 [POI2008]CLO

Description

(Byteotia) 城市有 (n) 个 (towns)，(m)条双向 (roads). 每条 (road) 连接两个不同的 (towns) ,没有重复的 (road) . 你要把其中一些(road) 变成单向边使得：每个 (town) 都有且只有一个入度

Input

第一行输入(n) (m) .(1leq nleq 100000),(1 leq m leq 200000) 下面 (M) 行用于描述 (M) 条边.

Output

(TAK) 或者 (NIE) 常做 (POI) 的同学,应该知道这两个单词的了...

Sample Input

4 5
1 2
2 3
1 3
3 4
1 4

Sample Output

TAK

上图给出了一种连接方式.

Solution

听说下午要讲并查集的各种玩法...
对于每一个连通块考虑，如果一个块没有环，那么这个连通块必然无法满足题目要求。

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

#define N 100001
#define rep(i, a, b) for (int i = a; i <= b; i++)

inline int read() {
	int x = 0, flag = 1; char ch = getchar(); while (!isdigit(ch)) { if (!(ch ^ '-')) flag = -1; ch = getchar(); }
	while (isdigit(ch)) x = (x << 1) + (x << 3) + ch - '0', ch = getchar(); return x * flag;
}

int fa[N]; bool tag[N];
int find(int x) { return fa[x] ? fa[x] = find(fa[x]) : x; }
int main() {
	int n = read(), m = read(); while (m--) {
		int u = read(), v = read(), x = find(u), y = find(v);
		if (x ^ y) fa[x] = y, tag[x] |= tag[y], tag[y] |= tag[x];
		else tag[x] = 1;
	}
	rep(i, 1, n) if (!tag[find(i)]) { puts("NIE"); return 0; }
	puts("TAK");
	return 0;
}