求助大佬 unordered_map + 并查集 WA 30pts!!
查看原帖
求助大佬 unordered_map + 并查集 WA 30pts!!
488827
Super_Supper楼主2022/7/27 00:03
#include <iostream>
#include <unordered_map>

using namespace std;
namespace IO { // 这里是输入和输出
template <typename _Ty>
bool R(_Ty& __cur) {
  cin >> __cur;
  return (bool)cin;
}

template <typename _Ty, typename... _Other>
bool R(_Ty& __cur, _Other&... __other) {
  cin >> __cur;
  R(__other...);
  return (bool)cin;
}

template <typename _Ty>
void W(_Ty __cur) {
  cout << __cur;
}

template <typename _Ty, typename... _Other>
void W(_Ty __cur, _Other... __other) {
  cout << __cur;
  W(__other...);
}

template <typename _Ty>
void P(_Ty __cur) {
  cerr << __cur;
}

template <typename _Ty, typename... _Other>
void P(_Ty __cur, _Other... __other) {
  cerr << __cur;
  P(__other...);
}
}  // namespace IO
using namespace IO;

constexpr int N = 1e9 + 5;

int t, n;

unordered_map<int, int> f;

int find(int x) {
  return x == f[x] ? x : f[x] = find(f[x]);
}

void merge(int i, int j) {
  int x = find(i), y = find(j);
  if (x != y) {
    f[x] = y;
  }
}

int main() {
  R(t);
  for (bool ans = 1; t--; ans = 1) {
    R(n);
    for (int k = 1, i, j, e; k <= n; k++) {
      R(i, j, e);
      f[i] = !f[i] ? i : f[i];
      f[j] = !f[j] ? j : f[j];
      f[i + N] = !f[i + N] ? i + N : f[i + N];
      f[j + N] = !f[j + N] ? j + N : f[j + N];
      if (e) {
        if (find(i + N) == j || find(j + N) == i) {
          ans = 0;
        } else {
          merge(i, j);
          merge(i + N, j + N);
        }
      } else {
        if (find(i) == find(j) || find(i + N) == find(j + N)) {
          ans = 0;
        } else {
          merge(i, j + N);
          merge(i + N, j);
        }
      }
    }
    W(ans ? "YES\n" : "NO\n");
  }
  return 0;
}
2022/7/27 00:03
加载中...