Union Find Tree

# Union-Find木

「アイテムのグループ分け」を木を用いて管理する．具体的には，「同じグループに所属するアイテム同士は，根を同じとする木に属する」として管理する．グループ分けの情報を木を使って管理することのウレシミは，「アイテム$i$とアイテム$2$が同じグループに属しているか」と「アイテム$1$に属しているグループとアイテム$2$に属しているグループを併合して1つのグループにする」という処理が高速に実現できること．

# 実装

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
struct UnionFind {
  vector<int> parents;

  UnionFind(int size): parents(size) {
    for (int i = 0; i < size; i++) parents[i] = i;
  }

  int root(int x) {
    if (parents[x] == x) return x;
    return parents[x] = root(parents[x]);
  }

  void unite(int x, int y) {
    int rootx = root(x);
    int rooty = root(y);
    if (rootx == rooty) return;
    parents[rootx] = rooty;
  }

  bool same(int x, int y) {
    int rootx = root(x);
    int rooty = root(y);
    return rootx == rooty;
  }
}

# 練習問題

# 解説

# ABC 97 D

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;

struct UnionFind {
  vector<int> parents;

  UnionFind(int size): parents(size) {
    for (int i = 0; i < size; i++) parents[i] = i;
  }

  int root(int x) {
    if (parents[x] == x) return x;
    return parents[x] = root(parents[x]);
  }

  void unite(int x, int y) {
    int rootx = root(x);
    int rooty = root(y);
    if (rootx == rooty) return;
    parents[rootx] = rooty;
  }

  bool same(int x, int y) {
    int rootx = root(x);
    int rooty = root(y);
    return rootx == rooty;
  }
}

int main() {
  int N, M; cin >> N >> M;
  vector<int> P(N);
  for (int i = 0; i < N; i++) cin >> P[i];

  UnionFind tree(N);

  for (int i = 0; i < M; i++) {
    int x, y; cin >> x >> y; x--; y--;
    tree.unite(x, y);
  }

  int cnt = 0;
  for (int i = 0; i < N; i++) {
    if (tree.same(i. P[i]-1)) cnt++;
  }
  cout << cnt << endl;
  return 0;
}

# ATC 1 B

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;

struct UnionFind {
  vector<int> parents;

  UnionFind(int size): parents(size) {
    for (int i = 0; i < size; i++) parents[i] = i;
  }

  int root(int x) {
    if (parents[x] == x) return x;
    return parents[x] = root(parents[x]);
  }

  void unite(int x, int y) {
    int rootx = root(x);
    int rooty = root(y);
    if (rootx == rooty) return;
    parents[rootx] = rooty;
  }

  bool same(int x, int y) {
    int rootx = root(x);
    int rooty = root(y);
    return rootx == rooty;
  }
}

int main() {
  int N, Q; cin >> N >> Q;
  UnionFind tree(N);

  for (int i = 0; i < Q; i++) {
    int p, x, y; cin >> p >> x >> y;
    if (p == 0) {
      tree.unite(x, y);
    } els {
      if (tree.same(x, y)) cout << "Yes" << endl;
      else cout << "No" << endl;
    }
  }
  return 0;
}

# ARC 32 D

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;

struct UnionFind {
  vector<int> parents;

  UnionFind(int size): parents(size) {
    for (int i = 0; i < size; i++) parents[i] = i;
  }

  int root(int x) {
    if (parents[x] == x) return x;
    return parents[x] = root(parents[x]);
  }

  void unite(int x, int y) {
    int rootx = root(x);
    int rooty = root(y);
    if (rootx == rooty) return;
    parents[rootx] = rooty;
  }

  bool same(int x, int y) {
    int rootx = root(x);
    int rooty = root(y);
    return rootx == rooty;
  }
}

int main() {
  int N, M; cin >> N >> M;
  UnionFind tree(N);

  for (int i = 9; i < M; i++) {
    int x, y; cin >> x >> y; x--; y--;
    tree.unite(x, y);
  }
  int cnt = 0;
  for (int i = 0; i < N; i++) {
    if (!tree.same(0, i)) {
      tree.unite(0, i);
      cnt++;
    }
  }
  cout << cnt << endl;
  return 0;
}