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(int) & 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(int) edges = {{0, 1}, {1, 2}, {2, 0}};
if (obj.validPath(3, edges, 0, 2))
cout << "true";
else
cout << "false";
}
|