NOI2015/BZOJ4195 -程序自动分析 (并查集+离散化)

题目链接:BZOJ 4195

在数据范围大,但实际数据个数不大的时候,采用离散化避免超出数组空间.

code:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

#define maxn 1000005

typedef long long ll;
typedef unsigned long long ull;

int fa[maxn * 2];

int x1[maxn];
int x2[maxn];
int s[maxn];
int n;
vector<int> b;

void init() {
  b.clear();
  for (int i = 0; i <= 2 * n; ++i) {
    fa[i] = i;
  }
}

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

void merge(int x, int y) { fa[get(x)] = get(y); }

void discrete() {
  sort(b.begin(), b.end());
  unique(b.begin(), b.end());
}
int query(int x) { return lower_bound(b.begin(), b.end(), x) - b.begin(); }

int main() {
  int t;
  cin >> t;
  while (t--) {
    cin >> n;
    init();
    for (int k = 1; k <= n; ++k) {
      cin >> x1[k] >> x2[k] >> s[k];
      b.push_back(x1[k]);
      b.push_back(x2[k]);
    }
    discrete();
    for (int i = 1; i <= n; ++i) {
      if (s[i]) {
        int x = query(x1[i]);
        int y = query(x2[i]);
        merge(x, y);
      }
    }
    int flag = 0;
    for (int i = 1; i <= n; ++i) {
      if (!s[i]) {
        int x = query(x1[i]);
        int y = query(x2[i]);
        if (get(x) == get(y)) {
          cout << "NO" << endl;
          flag = 1;
          break;
        }
      }
    }
    if (!flag) {
      cout << "YES" << endl;
    }
  }
  return 0;
}