我懵圈了,官方提供的第2个样例数据,我返回的也是`No`,为啥过不去!
查看原帖
我懵圈了,官方提供的第2个样例数据,我返回的也是`No`,为啥过不去!
675208
coder2009楼主2023/7/11 16:40

我懵圈了, 我的代码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;
}
2023/7/11 16:40
加载中...