PracticasProgramacionCompetitiva/disjointSet.cpp at main · AnahiSU/PracticasProgramacionCompetitiva · GitHub

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
/*
- Science is knowledge which we understand so well
  that we can teach it to a computer; and if we don’t
  fully understand something, it is an art to deal with it.
- El trabajo duro supera al talento cuando el talento no trabaja duro.
- Los desafios son los que hacen la vida interesante y superarlos es
  lo que hace a la vida significativa.
- Para sentirse vivo se necesita una meta en la que trabajar.
*/

typedef long long ll;
#define srt(a) sort((a).begin(),(a).end());
#define srtR(a) sort((a).rbegin(),(a).rend());

#include <bits/stdc++.h>
using namespace std;

struct unionFind {
   vector<int> p;
   int c;
   unionFind(int n) : p(n, -1), c(n) {}

   int find(int x) {
       if (p[x] == -1) return x;
       return p[x] = find(p[x]);
   }

   bool join(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return false;
        p[y] = x;
        c--;
        return true;
   }

   int size1() {
       return c-1;
   }
};

class disjoint_set {

	private:
		vector<int> parents;
		vector<int> sizes;

	public:
		disjoint_set(int size) : parents(size), sizes(size, 1) {
			for (int i = 0; i < size; i++) {
				parents[i] = i;
			}
		}

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

		bool unite(int x, int y) {
			int x_root = find(x);
			int y_root = find(y);
			if (x_root == y_root) return false;

			if (sizes[x_root] < sizes[y_root]) swap(x_root, y_root);
			sizes[x_root] += sizes[y_root];
			parents[y_root] = x_root;
			return true;
		}

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

};

signed main (){
    ios::sync_with_stdio(false);cin.tie(0);

    return 0;
}

//                   :-==-.                     .:..
//                .+%@@@@@@#-                -*%@@@@#+.
//              .%@@@@@@@@@@%*=--:.....::--+#@@@@@@@@@@@=
//              +@@@@@@@%*-.                 .-*%@@@@@@@%
//              +@@@@@%=.                       .=%@@@@@@.
//              -@@@@*.                           .+@@@@%
//               +@@+    ..                         =@@%:
//                -*  :*%@@@*.             :+#%#+.   +#:
//                =. =@@@*=+@%            :%@##@@@+  .+
//                + -@@@@.  #@:  :-----   *@=  +@@@+  +
//               .+ #@@@@#+*@%.  *@@@@%.  +@#:-#@@@@: =.
//               .=  @@@@@@@@+    .=*:     :@@@@@@@@= -:
//                + :**%@%*:     .-=+--     :#@@%**+  +
//                +.---:.                     .----- .=
//                 :=                               +.
//                    :=-.                     .-=:
//                           .:-----------:.