Atcoder ARC164B Switching Travel

称 \(c_u \not= c_v\) 的边 \((u, v)\) 为普通边，\(c_u = c_v\) 的边 \((u, v)\) 为特殊边。
能发现若满足条件则这个环应该是由一条特殊边和若干条普通便组成的（从特殊边的一个顶点出发一直经过普通边，最后走到特殊边的另一个顶点再走回来）。

于是若这个特殊边的两个顶点能只通过普通边相连通，这条边加上两个顶点路径上的若干条普通边就可以组成一个满足条件的环。
用并查集维护连通即可。

时间复杂度 \(O(m + n\log_2 n)\)。

// lhzawa(https://www.cnblogs.com/lhzawa/)
// Problem: B - Switching Travel
// Contest: AtCoder - AtCoder Regular Contest 164
// URL: https://atcoder.jp/contests/arc164/tasks/arc164_b
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int fa[N];
int getfa(int u) {
	return fa[u] == u ? u : (fa[u] = getfa(fa[u]));
}
void merge(int u, int v) {
	u = getfa(u), v = getfa(v);
	if (u == v) {
		return ;
	}
	fa[u] = v;
	return ;
}
int u[N], v[N];
int c[N];
int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++) {
		scanf("%d%d", &u[i], &v[i]);
	}
	for (int i = 1; i <= n; i++) {
		scanf("%d", &c[i]);
	}
	for (int i = 1; i <= n; i++) {
		fa[i] = i;
	}
	for (int i = 1; i <= m; i++) {
		if (c[u[i]] != c[v[i]]) {
			merge(u[i], v[i]);
		}
	}
	for (int i = 1; i <= m; i++) {
		if (c[u[i]] == c[v[i]] && getfa(u[i]) == getfa(v[i])) {
			printf("Yes\n");
			return 0;
		}
	}
	printf("No\n");
	return 0;
}