我懵圈了, 我的代码20测试点AC,26个测试点WA,但
官方提供的第2个样例数据,我返回的也是No
5 6
1 2
2 3
3 4
4 5
1 4
2 5
0 1 0 1 0
但提交的时候官方确是WA,为啥啊,请大神帮我看看我的代码吧。
我很郁闷,下面是我的代码。
#include <bits/stdc++.h>
using namespace std;
#define endl '\n';
struct UF {
vector<int> fa;
UF(int n) :
fa(n + 5) {}
void initialize(int n) {
for (int i = 1; i <= n; ++i) {
fa[i] = i; //要记得先将每个节点的祖宗节点更新为本身
}
}
int Find(int a) {
if (a != fa[a]) { //如果a的父节点不是本身,就往前找到其祖宗节点
fa[a] = Find(fa[a]); //往回返的时候把路上遍历过的所有节点更新为祖宗节点
}
return fa[a];
}
void Union(int x, int y) {
int a = Find(x);
int b = Find(y); //找到两个数的祖宗节点
if (a != b) {
fa[b] = a; //合并时只改其祖宗节点
}
}
bool find_union(int x, int y) { //判断两个数在不在一个集合里
int a = Find(x);
int b = Find(y);
if (a == b) {
return true;
} else {
return false;
}
}
};
struct edge {
int x, y, c;
} v[200005];
void best_coder() {
int n, m;
cin >> n >> m;
UF uf(n);
uf.initialize(n);
for (int i = 1; i <= m; ++i) {
cin >> v[i].x >> v[i].y;
}
for (int i = 1; i <= n; ++i) {
cin >> v[i].c;
}
for (int i = 1; i <= m; ++i) {
int a = v[i].x;
int b = v[i].y;
if (v[a].c != v[b].c) {
uf.Union(a, b);
}
}
bool is;
for (int i = 1; i <= m; ++i) {
int a = v[i].x;
int b = v[i].y;
if (v[a].c == v[b].c && uf.find_union(a, b)) {
is = true;
}
}
if (is) {
cout << "Yes" << '\n';
} else {
cout << "No" << '\n';
}
}
void happy_coder() {
}
int main() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// 小码匠
best_coder();
// 最优解
// happy_coder();
// 返回
return 0;
}