20pts 求助,并查集+map
查看原帖
20pts 求助,并查集+map
792364
hzx198楼主2024/3/10 05:55
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

map<ll, ll> f; // 并查集父节点
ll ne[1000005][2]; // 不相等的条件

ll getf(ll a) { return f[a] == a ? a : f[a] = getf(f[a]); }
void merge(ll a, ll b) { f[b] = getf(a); }

int main(void) {
  ll t;
  scanf("%lld", &t);
  while (t--) {
    // 清空
    f.clear();
    memset(ne, 0, sizeof(ne));
    ll n, cnt = 0;
    scanf("%lld", &n);
    while (n--) {
      ll i, j, e;
      scanf("%lld %lld %lld", &i, &j, &e);
      // 若 f 中没有就初始化
      if (f.count(i) == 0) f[i] = i;
      if (f.count(j) == 0) f[j] = j;
      if (e == 1) {
        if (getf(i) != getf(j)) merge(i, j);
      } else {
        cnt++;
        ne[cnt][0] = i, ne[cnt][1] = j; // 把不相等的条件先存起来
      }
    }
    // 最终判断
    bool flag = 1;
    for (ll i = 1; i <= cnt; i++) {
      if (getf(ne[i][0]) == getf(ne[i][1])) {
        flag = 0;
        break;
      }
    }
    puts(flag ? "YES" : "NO");
  }
  return 0;
}
2024/3/10 05:55
加载中...