题目链接：https://www.luogu.com.cn/problem/CF662B
题目大意：
有 (n) 个点 (m) 条边，边有颜色 —— 红色或蓝色。你可以对点进行操作，每操作一个点，与这个点相邻的所有边会变化颜色（红色变蓝色，蓝色变红色）。问：最少需要操作几次能够让边的颜色都一样（并输出最少需要操作的所有点的编号）。
解题思路：
可能存在多个连通块。首先我需要枚举将要变成的颜色，然后对于每一个连通块中第一个碰到的点，我枚举这个点要不要进行操作。
因为一条边连接两个点，这个点有没有操作直接影响了和它相邻的边要不要操作。同时一个点最多操作依次（操作两次就跟没操作一样了）。
所以，总的时间复杂度为 (O(4 cdot n))。
示例代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
struct Edge {
int u, v, c, cc, nxt; // cc表示原始的颜色
Edge() {}
Edge(int _u, int _v, int _c, int _nxt) { u = _u; v = _v; c = cc = _c; nxt = _nxt; }
} edge[maxn<<1];
int head[maxn], n, m, ecnt, tmp, sum[2];
vector<int> res[2], tmp_vec, vecs[2];
void init() {
ecnt = 0;
memset(head, -1, sizeof(int)*(n+1));
}
void addedge(int u, int v, int c) {
edge[ecnt] = Edge(u, v, c, head[u]); head[u] = ecnt ++;
edge[ecnt] = Edge(v, u, c, head[v]); head[v] = ecnt ++;
}
bool vis[maxn];
bool dfs(int u, bool paint, int c) {
vis[u] = true;
if (paint) {
tmp ++;
tmp_vec.push_back(u);
for (int i = head[u]; i != -1; i = edge[i].nxt) {
edge[i].c ^= 1;
edge[i^1].c ^= 1;
}
}
for (int i = head[u]; i != -1; i = edge[i].nxt) {
int v = edge[i].v;
if (edge[i].c != c) {
if (vis[v]) return false;
if (!dfs(v, true, c)) return false;
}
else if (!vis[v] && !dfs(v, false, c)) return false;
}
return true;
}
void recover(int u) {
vis[u] = false;
for (int i = head[u]; i != -1; i = edge[i].nxt) {
edge[i].c = edge[i^1].c = edge[i].cc;
int v = edge[i].v;
if (vis[v]) recover(v);
}
}
void handle(int u, int c, int id) {
tmp = 0;
int tmp1 = -1;
for (int i = 0; i < 2; i ++) vecs[i].clear();
tmp_vec.clear();
if (dfs(u, true, c)) {
tmp1 = tmp;
for (int i = 0; i < tmp1; i ++) vecs[0].push_back(tmp_vec[i]);
}
recover(u);
tmp = 0;
int tmp2 = -1;
tmp_vec.clear();
if (dfs(u, false, c)) {
tmp2 = tmp;
for (int i = 0; i < tmp2; i ++) vecs[1].push_back(tmp_vec[i]);
}
if (tmp1 == -1 && tmp2 == -1 ) sum[id] = -1;
else if (tmp2 == -1 || tmp1 != -1 && tmp1 < tmp2) {
sum[id] += tmp1;
for (int i = 0; i < tmp1; i ++) res[id].push_back(vecs[0][i]);
}
else {
sum[id] += tmp2;
for (int i = 0; i < tmp2; i ++) res[id].push_back(vecs[1][i]);
}
}
int main() {
scanf("%d%d", &n, &m);
init();
while (m --) {
int u, v, c;
char cc[2];
scanf("%d%d%s", &u, &v, cc);
c = (cc[0] == 'R');
addedge(u, v, c);
}
for (int i = 1; i <= n && sum[0] != -1; i ++) {
if (!vis[i]) handle(i, 0, 0);
}
for (int i = 1; i <= n; i ++) vis[i] = false;
for (int i = 0; i < ecnt; i ++) edge[i].c = edge[i].cc;
for (int i = 1; i <= n && sum[1] != -1; i ++) {
if (!vis[i]) handle(i, 1, 1);
}
if (sum[0] == -1 && sum[1] == -1) puts("-1");
else if (sum[1] == -1 || sum[0] != -1 && sum[0] < sum[1]) {
printf("%d
", sum[0]);
for (int i = 0; i < sum[0]; i ++) printf("%d ", res[0][i]);
}
else {
printf("%d
", sum[1]);
for (int i = 0; i < sum[1]; i ++) printf("%d ", res[1][i]);
}
return 0;
}