1pub struct DisjointSet(Vec<usize>);
2
3impl DisjointSet {
4 pub fn new(n: usize) -> Self { Self((0..n).collect()) }
5 pub fn unite(&mut self, u: usize, v: usize) -> bool {
6 if self.0[u] == self.0[v] {
7 return false;
8 }
9 let n = self.0.len();
10 for i in 0..n {
11 if self.0[i] == self.0[u] {
12 self.0[i] = self.0[v];
13 }
14 }
15 true
16 }
17 pub fn equiv(&self, u: usize, v: usize) -> bool {
18 self.repr(u) == self.repr(v)
19 }
20 pub fn repr(&self, u: usize) -> usize { self.0[u] }
21 pub fn count(&self, u: usize) -> usize {
22 let n = self.0.len();
23 (0..n).filter(|&i| self.0[i] == self.0[u]).count()
24 }
25}