leetcode

0 class UnionFind {

1 vector<int> root, rank;

2

3 public:

4 UnionFind(int n) : root(n), rank(n, 1) { iota(root.begin(), root.end(), 0); }

5

6 int find(int x) {

7 while (x != root[x])

8 x = root[x] = root[root[x]];

9 return x;

10 }

11

12 void join(int x, int y) {

13 x = find(x), y = find(y);

14

15 if (x != y) {

16 if (rank[x] > rank[y]) swap(x, y);

17

18 root[x] = y;

19 rank[y] += rank[x];

20 }

21 }

22 };

23

24 class Solution {

25 public:

26 bool validPath(int n, vector<vector<int>> &edges, int source, int destination) {

27 UnionFind uf(n);

28 for (auto &p : edges)

29 uf.join(p[0], p[1]);

30

31 return uf.find(source) == uf.find(destination);

32 }

33 };