题目传送门(BZOJ)
>原文链接<
BZOJ 2079

题意 :

给你一张图, 要求你黑白染色,

每个白点必须可以被一个黑点直接到达,

每个黑点也必须可以被一个白点直接到达

题解 :

首先若有某个联通块节点数量为1, 那么它肯定不符合条件

否则我们可以求出一棵生成树, 由于树是二分图, 直接黑白染色必定有解.

所以题目就是求是否有联通块节点数量为1

代码 :

#include <cstdio>#include <iostream>#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1000000, stdin), p1==p2)?EOF:*p1++)char buf[1000000], *p1, *p2; inline int rd() { int x = 0; char ch = nc(); while(!isdigit(ch)) ch = nc(); while(isdigit(ch)) x = ((x+(x<<2))<<1)+(ch^48), ch = nc(); return x;}bool v[200001];int main() { int n = rd(), m = rd(); register int i; for(i = 1; i <= m; i ++ ) v[rd()] = v[rd()] = 1; for(i = 1; i <= n; i ++ ) if(!v[i]) return puts("NIE"), 0; puts("TAK");}