aboutsummaryrefslogtreecommitdiff
path: root/find_path_graph.cpp
blob: 9f6c8ae12c05c3bdb470373ee7697bd1ada62460 (plain)
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
#include "leetcode.h"

class Solution {
public:
  bool validPath(int n, vvd & edges, int source, int destination) {
    vector<int> ds(n, -1);
    for (auto &e : edges) {
      int p1 = find(ds, e[0]), p2 = find(ds, e[1]);
      if (p1 != p2)
        ds[p2] = p1;
    }
    return find(ds, source) == find(ds, destination);
  }

private:
  int find(vector<int> &ds, int i) {
    return ds[i] < 0 ? i : ds[i] = find(ds, ds[i]);
  }
};

int main() {
  Solution obj;
  vvd edges = {{0, 1}, {1, 2}, {2, 0}};
  if (obj.validPath(3, edges, 0, 2))
    cout << "true";
  else
    cout << "false";
}