leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

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 };