70pts求助
查看原帖
70pts求助
748238
ghx0052楼主2024/4/2 21:52
#include <bits/stdc++.h>
using namespace std;

unordered_map<int, int> flag;
const int MAXN = 1e5 + 10;
int fa[MAXN * 2];

int Find(int x) {
    if (x == fa[x]) return x;
    return fa[x] = Find(fa[x]);
}

struct node {
    int op, x, y;
} a[100100];

bool cmp(node x, node y) {
    return x.op > y.op;
}

signed main() {
    freopen("P1955_2.in", "r", stdin);
    freopen("P1955_2.ans", "w", stdout);
    int t;
    cin >> t;
    while (t --) {
        flag.clear();
        int n, f = 0, cnt = 0;

        cin >> n;
        for (int i = 1; i <= n * 2; i ++) fa[i] = i;
        for (int i = 1; i <= n; i ++) 
            cin >> a[i].x >> a[i].y >> a[i].op;

        sort(a + 1, a + 1 + n, cmp);

        for (int i = 1; i <= n; i ++) {
            if (f) continue;

            if (!flag[a[i].x]) flag[a[i].x] = ++ cnt;
            if (!flag[a[i].y]) flag[a[i].y] = ++ cnt;

            int fx1 = Find(flag[a[i].x]), fx2 = Find(flag[a[i].x] + n);
            int fy1 = Find(flag[a[i].y]), fy2 = Find(flag[a[i].y] + n);
            
            if (a[i].op == 1) {
                if (fy1 == fx1 && a[i].x != a[i].y) {
                    cout << "NO\n";
                    f = 1;
                }
                fa[fx2] = fy2;
            }
            
            if (a[i].op == 0) {
                if (fy2 == fx2 || a[i].x == a[i].y) {
                    cout << "NO\n";
                    f = 1;
                }
                fa[fx1] = fy1;
            }
        }

        if (!f) cout << "YES\n";
    }
}
2024/4/2 21:52
加载中...