test/aoj/DSL_1_A.test.cpp

• View this file on GitHub
• Last update: 2021-04-15 20:24:09+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_A

Depends on

• Union-Find (datastructure/union-find-tree.hpp)

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_A"
#include "../../datastructure/union-find-tree.hpp"

#include <iostream>
using namespace std;
int main() {
  int n, q; cin >> n >> q;
  UnionFind uf(n);
  for (int i = 0; i < q; ++i) {
    int c, x, y; cin >> c >> x >> y;
    if (c == 0) { uf.unite(x, y); }
    else {
      if (uf.same(x, y)) cout << 1 << endl;
      else cout << 0 << endl;
    }
  }
}

#line 1 "test/aoj/DSL_1_A.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_A"
#line 1 "datastructure/union-find-tree.hpp"
/**
 * @title Union-Find
 */
#include <vector>

class UnionFind {
public:
  std::vector<int> data; // sizeとparを同時に管理する
  UnionFind(int size) : data(size, -1) {}
  int find(int x) { return data[x] < 0 ? x : data[x] = find(data[x]); }
  void unite(int x, int y) {
    int px = find(x);
    int py = find(y);
    if (px != py) {
      if (data[py] < data[px]) std::swap(px, py);
      data[px] += data[py]; data[py] = px;
    }
  }
  bool same(int x, int y) { return find(x) == find(y); }
  int size(int x) { return -data[find(x)]; }
};
#line 3 "test/aoj/DSL_1_A.test.cpp"

#include <iostream>
using namespace std;
int main() {
  int n, q; cin >> n >> q;
  UnionFind uf(n);
  for (int i = 0; i < q; ++i) {
    int c, x, y; cin >> c >> x >> y;
    if (c == 0) { uf.unite(x, y); }
    else {
      if (uf.same(x, y)) cout << 1 << endl;
      else cout << 0 << endl;
    }
  }
}

Back to top page