CF662B Graph Coloring

很一眼的题

考虑枚举最后所有边的颜色，然后每个点是否变化可以用一个bool变量表示，就是个很典的2-SAT问题，根据当前边和目标的颜色相同与否连边即可

但这题的难点在于要找一个操作次数最少的方案，乍一看很难搞

但如果你对图论和2-SAT那一套理解比较深的话就很容易发现，这道题中所有边都是双向的

这就意味着当选择了某个点后，它所在的联通块的所有点都要被选，那么直接统计下每个联通块内要操作的次数，每次选较少的那边即可

算是个比较有意思的trick，可以mark一下

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int n,m,x[N],y[N],c[N],dfn[N],low[N],stk[N],col[N],vis[N],ext[N],top,idx,scc;
vector <int> v[N],id[N]; char ch[10];
inline void Tarjan(CI now)
{
	dfn[now]=low[now]=++idx; stk[++top]=now; vis[now]=1;
	for (int to:v[now]) if (!dfn[to]) Tarjan(to),low[now]=min(low[now],low[to]);
	else if (vis[to]) low[now]=min(low[now],dfn[to]);
	if (low[now]==dfn[now])
	{
		col[now]=++scc; vis[now]=0;
		if (now<=n) id[scc].push_back(now);
		while (stk[top]!=now)
		{
			col[stk[top]]=scc;
			if (stk[top]<=n) id[scc].push_back(stk[top]); vis[stk[top--]]=0;
		}
		--top;
	}
}
inline void addedge(CI x,CI y)
{
	v[x].push_back(y); v[y].push_back(x);
}
inline vector <int> solve(CI tar)
{
	RI i; for (i=1;i<=2*n;++i) v[i].clear(),id[i].clear(),dfn[i]=ext[i]=0;
	vector <int> ans; for (i=1;i<=m;++i)
	if (c[i]==tar) addedge(x[i],y[i]),addedge(x[i]+n,y[i]+n);
	else addedge(x[i],y[i]+n),addedge(x[i]+n,y[i]);
	for (idx=scc=0,i=1;i<=2*n;++i) if (!dfn[i]) Tarjan(i);
	for (i=1;i<=n;++i) if (col[i]==col[i+n]) return ans.resize(n),ans;
	for (i=1;i<=n;++i)
	{
		if (ext[col[i]]) continue; ext[col[i]]=ext[col[i+n]]=1;
		if (id[col[i]].size()<id[col[i+n]].size())
		for (auto it:id[col[i]]) ans.push_back(it); else
		for	(auto it:id[col[i+n]]) ans.push_back(it);
	}
	return ans;
}
inline void print(vector <int>& ans)
{
	if (ans.size()==n) return (void)(puts("-1"));
	printf("%d\n",ans.size());
	for (auto it:ans) printf("%d ",it);
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d%d",&n,&m),i=1;i<=m;++i)
	scanf("%d%d%s",&x[i],&y[i],ch),c[i]=ch[0]=='B';
	auto A1=solve(1),A2=solve(0);
	if (A1.size()<A2.size()) print(A1); else print(A2);
	return 0;
}