Solution

Vol7

BZOJ1116

解决的关键是定理：有解的充分必要条件是任意节点所在的联通分量都有至少一个环。

先证充分性，假设目前的联通分量有且仅有一个极大环，极大环自身上的点显然有解，然后我们将所有和极大环相连的点所依靠的那条边我们都改为指向环外点。于是剩下的变成了很多棵树， 且根节点已经解决了入度问题， 然后将所有边改为指向子节点即可。对于不仅有一个环的情况，归纳法即可。

再证必要性，假设目前的联通分量没有环，则其是树，考虑根节点，必然有其个子节点指向它，取该子节点继续讨论，最后会归纳于某个叶子节点，而叶子节点是找不到子节点指向它的。

于是问题就很简单了，我们维护每一个节点所在的联通分量是否有环即可，这一步我们用并查集维护。

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
int fa[100005];
bool can[100005];
int n,m;
int find(int a)
{
    if(fa[a]!=a)
        fa[a]=find(fa[a]);
    return fa[a];
}
void Readdata()
{
    freopen("loli.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        fa[i]=i;
    memset(can,false,sizeof(can));
    int a,b;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&a,&b);
        int fx=find(a),fy=find(b);
        if(fx==fy)
            can[fx]=true;
        else{
            fa[fx]=fy;
            can[fy]|=can[fx];
        }
    }
}
void Solve()
{
    for(int i=1;i<=n;i++){
        int fx=find(i);
        if(!can[fx]){
            printf("NIE\n");
            return;
        }
    }
    printf("TAK\n");
}
void Close()
{
    fclose(stdin);
    fclose(stdout);
}
int main()
{
    Readdata();
    Solve();
    Close();
    return 0;
}