D. Edge Split #819 div1+2

Split #819 div1+2"/>

D. Edge Split #819 div1+2

Problem - D - Codeforces

题意是给你n个点m条边（注意这里的点边限制m<=n+2，是做这个题的关键！！），然后让你红蓝染色，然后让你a+b最小，ab分别是一个图把蓝色和红色分别抽出来看连通块的个数

这个题是个构造题吧，然后把最小生成树的知识点也复习了一遍

首先可以看出是不可能有环的，不管是红色的还是蓝色的，然后在没有环的基础上，连接一个点，连通分量就-1。所以很容易能想到，任意构造一个最小生成树，可以保证连接的连通分量是最大的

这时候需要分类讨论了：

①首先，当m<=n+1的时候，在构造最小生成树的情况下是绝对不可能出现环的，（最小生成树：把边从小到大排序，然后把不是一个集合的放入一个集合，可以看出最小生成树是绝对不可能出现环的），所以这种情况可以放心大胆的写，构造的最小生成树就是1，以外的是0

②不满足这个条件的，因为总的限制是m<=n+2，所以如果蓝色的形成环的话，那不是最优解，要改一下：把环里的任意一条边变成红色，这个时候不出意外红色是个环了，然后把改的这个边的所有邻边都变成蓝色，这样也破坏了红色的环。那怎么改呢，红色的本质是不在一个集合的划定在一个集合里面，本身就在这个集合的是蓝色，先把任意的一条边变成红色，两者在一个集合里面，所以按照原来顺序进行构造，当遇到原来顺序，两者已经在一个集合了，所以邻边是蓝色（这里需要一点点证明的哈），具体看代码~（我感觉想的也是挺费劲的...），为了方便理解，附一张图

然后贴个代码~

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#define IOS ios::sync_with_stdio(false), cin.tie(0);
#include<iostream>
#include<map>
#include<set> 
#include<cstdio>
#include<cstring>
#include<vector>
#include<stack>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> PAII;
const int N=2e6+10,M=5050,INF=1e9,mod=19980829;
int p[N];
int h[N],ne[N],e[N],idx,x[N],y[N];
set<int> s;
int find(int x)
{if(p[x]!=x) p[x]=find(p[x]);return p[x];
}
signed main(){IOS;int T;//T=1;cin>>T;while(T--){	s.clear();int n,m;cin>>n>>m;for(int i=1;i<=n;i++) h[i]=-1,p[i]=i;for(int i=1;i<=m;i++)cin>>x[i]>>y[i];if(m<=n+1)//需要构造出一个最小生成树，这个关系必不可能形成环 {for(int i=1;i<=m;i++){int xx=find(x[i]),yy=find(y[i]);if(xx!=yy){p[xx]=yy;cout<<"1";}else cout<<"0";}cout<<"\n";continue;}string ch;int now;for(int i=1;i<=m;i++){int xx=find(x[i]),yy=find(y[i]);if(xx!=yy){p[xx]=yy;ch+='1';}else{s.insert(x[i]);s.insert(y[i]);ch+='0';now=i;}}if(s.size()==3){for(int i=1;i<=n;i++) p[i]=i;int x1=find(x[now]),y1=find(y[now]);p[x1]=y1;for(int i=1;i<=m;i++){if(now==i){cout<<"1";continue;}int xx=find(x[i]),yy=find(y[i]);if(xx!=yy){p[xx]=yy;cout<<"1";}else cout<<"0";}cout<<"\n";}else cout<<ch<<"\n";}return 0;
}
/**/