1971.cpp (735B)
1 class UnionFind { 2 vector<int> root, rank; 3 4 public: 5 UnionFind(int n) : root(n), rank(n, 1) { iota(root.begin(), root.end(), 0); } 6 7 int find(int x) { 8 while (x != root[x]) 9 x = root[x] = root[root[x]]; 10 return x; 11 } 12 13 void join(int x, int y) { 14 x = find(x), y = find(y); 15 16 if (x != y) { 17 if (rank[x] > rank[y]) swap(x, y); 18 19 root[x] = y; 20 rank[y] += rank[x]; 21 } 22 } 23 }; 24 25 class Solution { 26 public: 27 bool validPath(int n, vector<vector<int>> &edges, int source, int destination) { 28 UnionFind uf(n); 29 for (auto &p : edges) 30 uf.join(p[0], p[1]); 31 32 return uf.find(source) == uf.find(destination); 33 } 34 };