Cf662b graph coloring problem solution

Subject portal

The main idea of the topic

Here's an undirected graph , Each edge in the figure is blue or red , Let you choose one point at a time , The color of the edge connected to this point will be reversed （ Red turns blue , Blue to red ）, The scheme of finding the minimum number of steps makes the color of all the final edges the same .

Ideas

It seems that no \(2-sat\) The antithesis of , Then I'll do it .

First, discuss by category ： Or they all turn red , Or they all turn blue .

If the color of an edge is the same as what we currently expect , Then either choose both points , Or don't choose , So if a point is not selected , Then don't choose the other point , One click , Another point should also be chosen , Just build a map , Here's the picture .

So in the same way , If the color of an edge is different from the desired color , therefore , If you click on one , The other point cannot be selected , If a point is not selected , Then the other point must be selectable , Picture words , A little .

So we can sort out a \(2-sat\) Model of .

Judge the situation without solution , This is it. \(2-sat\) Classic operation of , Judge \(u,u'\) Whether it is in a strong connected component .

For the case with a solution , And output the solution , So, since this graph is symmetrical up and down , So that is to say , If you choose \(i_1,i_2\dots,i_m,j_1',j_2'\dots,j_{m'}'\) This strongly connected component , Then you must not choose it , choose \(i_1',i_2'\dots,i_m',j_1,j_2\dots,j_{m'}\) This strongly connected component , So in order to select as few as possible , So look at these two things \(u'\) Who has more, who has less , Add it to the answer , Then put the selected points into the final scheme .

See the code for details. .

I don't know why there are so many details in other questions , Maybe my method has no details .

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
void read(){}// Let's learn , It can be used like this :read(a,b,c,……,n);
template<typename _Tp,typename... _Tps>
void read(_Tp &x,_Tps &...Ar){
	x=0;char c=getchar();bool flag=0;
	while(c<'0'||c>'9')flag|=(c=='-'),c=getchar();
	while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
	if(flag)x=-x;
	read(Ar...);
}
const int N=1e5+10;
int n,m;
struct zj{
	int u,v,w;
}a[N];
struct edges{
	int to,nex;
}edge[N*4];// Note that for each edge , To build two two-way sides , So the size should be open  4  times 
int head[N*2],kk;
void addedge(int u,int v){// Basic operation of chained forward star , Directly build a two-way edge 
	edge[++kk]=(edges){v,head[u]};head[u]=kk;
	edge[++kk]=(edges){u,head[v]};head[v]=kk;
}
int dfn[N*2],low[N*2],s[N*2],top,cnt,scc[N*2],scct;// Don't forget to count  2  times 
void tarjan(int u){//tarjan  Shrink point template 
	dfn[u]=low[u]=++cnt;s[++top]=u;
	for(int i=head[u];i;i=edge[i].nex){
		int v=edge[i].to;
		if(!dfn[v])tarjan(v),low[u]=min(low[u],low[v]);
		else if(!scc[v])low[u]=min(low[u],low[v]);
	}
	if(dfn[u]==low[u]){
		++scct;
		while(s[top]!=u)scc[s[top--]]=scct;
		scc[s[top--]]=scct;
	}
}
int cnt1,cnt2,k1[N],k2[N],s1[N],s2[N];// Record  dfs  Arrived in  u  and  u'  Quantity and number of 
bool vis[N];
void dfs(int u){
	if(vis[(u-1)%n+1])return;//1,2,……,n  unchanged , n+1,n+2,……,n+n  become  1,2,……,n
	vis[(u-1)%n+1]=1;u<=n?(k1[++cnt1]=u):(k2[++cnt2]=u-n);
	for(int i=head[u];i;i=edge[i].nex){
		int v=edge[i].to;
		dfs(v);
	}
}
int get(){
	int i;char c[5];bool flag1,flag2;int ans1=0,ans2=0;
	for(read(n,m),i=1;i<=m;i++)read(a[i].u,a[i].v),scanf("%s",c),a[i].w=(c[0]=='R');// Proper line pressing can enhance code readability (
	for(i=1;i<=m;i++)a[i].w?(addedge(a[i].u,a[i].v),addedge(a[i].u+n,a[i].v+n)):(addedge(a[i].u,a[i].v+n),addedge(a[i].u+n,a[i].v));// This is what I explained above 
	for(i=1;i<=n*2;i++)if(!dfn[i])tarjan(i);
	for(flag1=1,i=1;i<=n;i++)if(scc[i]==scc[i+n])flag1=0;
	if(flag1)for(i=1;i<=n;i++){
		if(vis[i])continue;
		cnt1=cnt2=0;
		dfs(i);
		if(cnt1<cnt2){// have a look  u,u'  Choose whichever is less 
			ans1+=cnt1;
			while(cnt1)s1[++s1[0]]=k1[cnt1--];
		}
		else{
			ans1+=cnt2;
			while(cnt2)s1[++s1[0]]=k2[cnt2--];
		}
		// You can't write this to save code :
		//if(cnt1>cnt2)swap(k1,k2),swap(cnt1,cnt2);
		//ans1+=cnt1;
		//while(cnt1)s1[++s1[0]]=k1[cnt1--];
		// This leads to complexity becoming  O(n^2), direct  T  fly 
	}
	//----------------- These are all cases of turning blue -----------------
	memset(head,0,sizeof(head));kk=0;
	memset(dfn,0,sizeof(dfn));cnt=0;
	memset(low,0,sizeof(low));
	memset(scc,0,sizeof(low));scct=0;
	memset(s,0,sizeof(s));top=0;
	memset(vis,0,sizeof(vis));
	//----------------- Be sure to empty -----------------
	for(i=1;i<=m;i++)a[i].w?(addedge(a[i].u+n,a[i].v),addedge(a[i].u,a[i].v+n)):(addedge(a[i].u,a[i].v),addedge(a[i].u+n,a[i].v+n));
	for(i=1;i<=n*2;i++)if(!dfn[i])tarjan(i);
	for(flag2=1,i=1;i<=n;i++)if(scc[i]==scc[i+n])flag2=0;
	if(flag2)for(i=1;i<=n;i++){
		cnt1=cnt2=0;
		dfs(i);
		if(cnt1<cnt2){
			ans2+=cnt1;
			while(cnt1)s2[++s2[0]]=k1[cnt1--];
		}
		else{
			ans2+=cnt2;
			while(cnt2)s2[++s2[0]]=k2[cnt2--];
		}
	}
	//----------------- These are the conditions that all turn red -----------------
	if(!flag1&&!flag2)return printf("-1"),0;// There is no solution in both cases 
	if(!flag1||(flag2&&s1[0]>s2[0]))swap(s1,s2);// If the first case has no solution or the first case is not as good as the second case , Then choose the second 
	for(printf("%d\n",s1[0]),i=1;i<=s1[0];i++)printf("%d ",s1[i]);
	return 0;// Perfect flowers 
}
int main(){
	return get();// The main function line , It is mainly convenient for multiple groups of test data or switches  freopen, Otherwise, you have to mark the roller and write it out , It's too troublesome !
}

Warm reminder

If there is any clerical error , Comment or chat about me in private , I hope that helps

thank you --zhengjun