P3465题解

Heart_Of_Iron_4 · 2024-12-10 20:20:50 · 题解

搞不懂为啥都用的基环树qwq
这题和P1640很相似。既然不算无向边，把边看成点，跑一遍二分图匹配，确保每个点都匹配上就行了。
（话说为啥我搜并查集的题目出来的都是二分图匹配啊）
代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
namespace IO{
    char ibuf[(1<<20)+1],*iS,*iT;
#if ONLINE_JUDGE
#define gh() (iS==iT?iT=(iS=ibuf)+fread(ibuf,1,(1<<20)+1,stdin),(iS==iT?EOF:*iS++):*iS++)
#else
#define gh() getchar()
#endif
    inline long long read(){
        char ch=gh();
        long long x=0;
        bool t=0;
        while(ch<'0'||ch>'9')   t|=ch=='-',ch=gh();
        while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=gh();
        return t?-x:x;
    }
}
using namespace IO;
int n,m,tag[314514],p[314514],t1,t2,e[314514][2],mc[314514];
vector<int> g[314514];
inline bool xyl(int x,int y)
{
    if(tag[x]==y)return 0;
    tag[x]=y;
    for(auto i:g[x])
    {
        if((p[i]==0)||(xyl(p[i],y)))
        {
            p[i]=x;
            mc[i]=x;
            mc[x]=i;
            return 1;
        }
    }
    return 0;
}
signed main()
{
    n=read();m=read();
    //dot:t->t edge:t->t+n
    for(int i=1;i<=m;++i)
    {
        t1=read();
        t2=read();
        g[t1].push_back(i+n);
        g[t2].push_back(i+n);
        g[i+n].push_back(t1);
        g[i+n].push_back(t2);
        e[i][0]=t1;
        e[i][1]=t2;
    }
    for(int i=1;i<=n;++i)
    {
        if(xyl(i,i)==0)
        {
            printf("NIE\n");
            exit(0);
        }
    }
    printf("TAK\n");
    for(int i=1;i<=n;++i)
    {
        if(e[mc[i]-n][0]==i)printf("%lld\n",e[mc[i]-n][1]);
        else printf("%lld\n",e[mc[i]-n][0]);
    }
    return 0;
}