[文章目录]
Description
Byteotia城市有n个 towns m条双向roads. 每条 road 连接 两个不同的 towns ,没有重复的road. 你要把其中一些road变成单向边使得：每个town都有且只有一个入度 1 <= n<= 100000,1 <= m <= 200000
并查集模拟二分图匹配。
一颗树一定是只有一个点没有入度。一个边数大于点数的联通图一定全部满足条件。
并查集维护联通性以及树上没有入度的点是谁即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 100100
int n,m,fa[N];
bool vis[N];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) fa[i]=i;
int x,y;
while(m--)
{
scanf("%d%d",&x,&y);
if(find(x)==find(y)) vis[fa[x]]=1;
else
{
vis[fa[y]]|=vis[fa[x]];
vis[fa[x]]=1;
fa[fa[x]]=fa[y];
}
}
for(int i=1;i<=n;++i) if(!vis[i])
{
puts("NIE");
return 0;
}
puts("TAK");
return 0;
}