题解：CF1726D Edge Split

Amoribus · 2026-03-31 19:51:13 · 题解

观察到，c_1+c_2 取到最小值，当且仅当红边组成的图和蓝边组成的图都是森林。由于 n-1\leq m\leq n+2，我们直接随机打乱边，用并查集维护生成树，并判断剩下的边是否组成一个三元环即可。如果不满足条件就再打乱。稍微卡一下常就能过了。

#include<bits/stdc++.h>
using namespace std;
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define int long long
const int N=2e5+7;
int T,n,m,ans[N],ANS[N],tt;
vector<int> e[N];
inline int read(){
    int w=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar();
    return w*f;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x<10) putchar(x+'0');
    else write(x/10),putchar(x%10+'0');
}
struct dsu{
    int fa[N];
    void init(int n){
        rep(i,1,n) fa[i]=i;
    }
    int find(int u){
        return (fa[u]==u)?u:fa[u]=find(fa[u]);
    }
    void merge(int u,int v){
        u=find(u),v=find(v);
        if(u!=v) fa[u]=v;
    }
    bool is(int u,int v){
        return find(u)==find(v);
    }   
}d1,d2;
struct node{
    int u,v,id;
}E[N];
void solve(){
    n=read(),m=read();
    tt=0;
    d1.init(n);
    d2.init(n);
    rep(i,1,m) ans[i]=0;
    rep(i,1,m){
        int u,v;
        u=read(),v=read();
        E[i]={u,v,i};
    }
    while(1){
        d1.init(n);d2.init(n);
        random_shuffle(E+1,E+m+1);
        rep(i,1,n) ans[i]=0;
        bool flag=1;
        rep(i,1,m){
            int u=E[i].u,v=E[i].v;
            if(!d1.is(u,v)) d1.merge(u,v);
            else ans[i]=1;
        }
        rep(i,1,m){
            int u=E[i].u,v=E[i].v;
            if(ans[i]==1){
                if(!d2.is(u,v)) d2.merge(u,v);
                else{
                    flag=0;
                    break;
                }
            }
        }
        if(flag==0) continue;
        rep(i,1,m){
            int u=E[i].u,v=E[i].v;
            ANS[E[i].id]=ans[i];
        }
        rep(i,1,m){
            write(ANS[i]);
        }
        cout<<"\n";
        return;
    }
}
signed main()
{
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}