Description：

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

$1\le n\le 10^5$

Solution：

发现一个联通块中只要边数 $\ge$ 点数就有解，并查集判断即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define MAXN 100010

int f[MAXN],cnt[MAXN],siz[MAXN];

int find(int x){return (x == f[x] ? x : f[x] = find(f[x]));}

int n,m;

bool v[MAXN];

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)

	{

		f[i] = i;

		siz[i] = 1;

	}

	int a,b;

	scanf("%d",&m);

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d",&a,&b);

		int p = find(a),q = find(b);

		if(p == q)

		{

			++cnt[p];

			continue;

		}

		f[p] = q;cnt[q] = cnt[q] + cnt[p] + 1;

		siz[q] = siz[q] + siz[p];

	}

	bool tag = true;

	for(int i = 1;i <= n;++i)

	{

		if(v[find(i)])continue;

		int p = find(i);

		v[p] = true;

		if(cnt[p] < siz[p])

		{

			tag = false;

			break;

		}

	}

	if(tag)puts("TAK");

	else puts("NIE");

	

	return 0;

}