并查集

提供一种只需使用并查集的好写的方法。

统一蓝和统一红只有一个取反的差别，以下默认全部统一为蓝。

一条蓝边，它的两个端点要么都选，要么都不选。

一条红边，它的两个端点只选择其中之一。

于是对每个点建立两个事件“它选”和“它不选”，可以用诸如 $i,i+n$ 的一类方法记录，以下以 $i$ 表示选，$i+n$ 表示不选。

按照上面的条件，设一条边两个端点为 $(u,v)$。可以发现：

一条蓝边，加入无向边 $(u,v),(u+n,v+n)$。

一条红边，加入无向边 $(u,v+n),(u+n,v)$。

到了这一步，大部分题解使用了 $\rm 2-SAT$ 判定。

但其实这些条件都是双向的，并查集就可以实现判断，一个连通块内的事件必须同时发生。

于是贪心地选择一下操作最少连通块就好了，甚至不用建图，也没有啥细节。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
#define rep(a,b,c) for(int c(a);c<=(b);++c)
#define drep(a,b,c) for(int c(a);c>=(b);--c)
using namespace std;
inline int read()
{
	int res=0;char ch=getchar();while(ch<'0'||ch>'9')ch=getchar();
	while(ch<='9'&&ch>='0')res=res*10+(ch^48),ch=getchar();return res;
}
inline bool Get(){char c;do c=getchar();while(c!='R'&&c!='B');return c=='R';}
const int N=1e5+10;int fa[N<<1],U[N],V[N],sz[N<<1];bool W[N],vis[N<<1];int n,m;
inline int fnd(int x){return fa[x]==x?x:fa[x]=fnd(fa[x]);}
inline void merge(int x,int y)
{
	int X=fnd(x),Y=fnd(y);if(X==Y)return;
	fa[X]=Y;sz[Y]+=sz[X];
}
vector<int> a[2];
inline bool work(vector<int> &ans)
{
	memset(vis+1,0,n<<1);
	rep(1,n<<1,i)fa[i]=i,sz[i]=(i<=n);
	rep(1,m,i)
	{
		int u=U[i],v=V[i];
		if(W[i])merge(u,v),merge(u+n,v+n);
		else merge(u+n,v),merge(u,v+n);
	}
	rep(1,n,i)if(fnd(i)==fnd(i+n))return false;
	rep(1,n,i)
	{
		int u=fnd(i),v=fnd(i+n);
		if(!vis[u]&&!vis[v])
		{
			if(sz[u]<sz[v]){ans.push_back(i);vis[v]=true;}
			else vis[u]=true;
		}
		else{if(vis[v])ans.push_back(i);}
	}
	return true;
}
inline void print(vector<int> &a)
{
	printf("%d\n",int(a.size()));
	for(int v:a)printf("%d ",v);puts("");
}
int main()
{
	n=read();m=read();rep(1,m,i){U[i]=read();V[i]=read();W[i]=Get();}
	bool f1=work(a[0]);
	rep(1,m,i)W[i]^=1;
	bool f2=work(a[1]);
	if(!f1&&!f2)return puts("-1"),0;
	if(!f1||!f2){if(f1)print(a[0]);else print(a[1]);return 0;}
	if(a[0].size()>a[1].size())print(a[1]);else print(a[0]);
}