Basic

Luogu P3367

Path Compression && Union by rank

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
using namespace std;
const int maxn = 10010;
int fa[maxn];
int ranks[maxn];
int n, m;

void init(int n) { // Initialize
  for (int i = 1; i <= n; i++) {
    fa[i] = i;
    ranks[i] = 1;
  }
}

int find_1(int k) {                              // Find（Recursion）
  return k == fa[k] ? k : fa[k] = find(fa[k]);   // Only add a few characters
}

int find(int k) { // Find (Without Recursion) (To prevent Stack_Overflow)
  int root = k;
  while (fa[root] != root)
    root = fa[root]; // Find the root node
  int i = k, tmp;
  while (i != root) {
    tmp = fa[i];  // Use tmp to record fa[i]_origin
    fa[i] = root; // Change the set of elements on the path to the root node
    i = tmp;
  }
  return root;
}

void Union(int x, int y) { // Optimizing Union
  x = find(x);
  y = find(y);
  if (x == y)
    return;
  if (ranks[x] < ranks[y]) 
    swap(x, y); // Guarantee the rank of x is higher than that of y
  fa[y] = x;    
  // When UNION, let the root with smaller rank point to the root with larger rank.
  ranks[x]+=ranks[y];
}


int check(int x, int y) {
  return (find(x) == find(y));
}

int main() {
  cin >> n >> m;
  init(n);
  while (m--) {
    int order, x, y;
    cin >> order >> x >> y;
    if (order == 1)
      Union(x, y);
    else if (check(x, y))
      cout << "Y\n";
    else
      cout << "N\n";
  }
  return 0;
}

Weighted

Luogu P1196

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
49
50
51
#include <iostream>
#include <cmath>
using namespace std;
const int maxn = 30010;
int t;
int fa[maxn], value[maxn], ranks[maxn];

void init() {
    for (int i = 1; i < maxn; i++) {
        fa[i] = i;
        ranks[i] = 1;
        value[i] = 0;
    }
}

int find(int k) {
    //When x and y are in the same line,value[k] saves the number of warships before k
    //Hence the number of warships between x and y is abs(value[y] - value[x]) - 1
    if (k == fa[k]) return k;
    int root = find(fa[k]);
    value[k] += value[fa[k]]; //Update
    return fa[k] = root;     //Path Compression
}

void Union(int x, int y) {
    x = find(x);
    y = find(y);
    fa[x] = y;
    value[x] = ranks[y];
    ranks[y] += ranks[x];//Record Size
}

int check(int x, int y) {
    return find(x) == find(y);
}

int main() {
    cin >> t;
    init();
    while (t--) {
        char ch;
        int x, y;
        cin >> ch >> x >> y;
        if (ch == 'M') Union(x, y);
        else if (check(x, y))
            cout << abs(value[y] - value[x]) - 1 << "\n";
        else
            cout << "-1\n";
    }
    return 0;
}

Persistent

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <iostream>
#define mid (l + r) >> 1
using namespace std;
const int maxn = 200010;
int n, m, cnt_tree = 0,cur;
int root[maxn], fa[maxn << 5], ranks[maxn << 5];

struct node {
    int l, r;
} tree[maxn << 5];

inline int read( ){ //fast read
    register int x = 0, t = 1; //improve efficiency
    register char c = getchar();
    while(c < '0' || c > '9') {if(c=='-')t=-1;c=getchar();}
    while(c >= '0' && c <= '9') {x=(x<<1)+(x<<3)+(c-48);c=getchar();} //Equal to x = x * 10 + c -'0';
    return x*t;
}

int build(int l, int r) {
    int rt = ++cnt_tree;
    if (l == r) {
        fa[rt] = l;
        ranks[rt] = 1;
        return rt;
    }
    int m = mid;
    tree[rt].l = build(l, m);
    tree[rt].r = build(m + 1, r);
    return rt;
}

int update(int pre, int x,  int val, int l, int r) {
    int rt = ++cnt_tree; //dynamic new node
    tree[rt] = tree[pre];
    ranks[rt] = ranks[pre];
    fa[rt] = fa[pre];
    if (l == r ) {
        fa[rt] = val;
        return rt;
    }
    int m = mid;
    if (x <= m)
        tree[rt].l = update(tree[pre].l, x, val, l, m);
    else
        tree[rt].r = update(tree[pre].r, x, val, m + 1, r);
    return rt;
}

int update_depth(int pre, int x, int l,int r){
    int now = 0;
    if (pre == root[cur]) now = pre;
    else now = ++cnt_tree;
    tree[now] = tree[pre];
    ranks[now] = ranks[pre];
    fa[now] = fa[pre];
    if (l == r) {
        ranks[now]++;
        return now;
    }
    else{
        int m = mid;
        if (x <= m) tree[now].l = update_depth(tree[pre].l, x,l,m);
        else tree[now].r = update_depth(tree[pre].r, x,m+1,r);
    }
    return now;
}

int query(int x, int rt, int l, int r) {
    if (l == r ) return rt;
    int m = mid;
    return (x <= m) ? query(x, tree[rt].l, l, m) : query(x, tree[rt].r, m + 1, r);
}

int find(int k) {
    int get_fa = query(k, root[cur], 1, n);
    return (k == fa[get_fa]) ? get_fa : find(fa[get_fa]);
}


void Union(int x, int y) {
    if (ranks[x] < ranks[y]) swap(x, y);                           // Guarantee the rank of x is higher than that of y
    root[cur] = update(root[cur], fa[y], fa[x], 1,n);//similar to fa[y] = x;
    if (ranks[x] == ranks[y]) update_depth(root[cur], fa[x], 1,n);
}

int main() {
    n = read();
    m = read();
    root[0] = build(1, n);
    int opt, x, y;
    for (int i = 1; i <= m; i++) {
        opt = read();
        root[i] = root[i - 1];
        cur = i;
        if (opt == 1) {
            x = read();
            y = read();
            x = find(x);
            y = find(y);
            if (fa[x] != fa[y]) Union(x, y);
        } else if (opt == 2) {
            x = read();
            root[i] = root[x];
        } else {
            x = read();
            y = read();
            x = find(x);
            y = find(y);
            if (x == y) puts("1");
            else puts("0");
        }
    }
    return 0;
}