BZOJ-1116: [POI2008]CLO

[文章目录]

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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注