diff options
author | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
---|---|---|
committer | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
commit | d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch) | |
tree | 96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /find_path_graph.cpp | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'find_path_graph.cpp')
-rw-r--r-- | find_path_graph.cpp | 28 |
1 files changed, 28 insertions, 0 deletions
diff --git a/find_path_graph.cpp b/find_path_graph.cpp new file mode 100644 index 0000000..0fae12b --- /dev/null +++ b/find_path_graph.cpp @@ -0,0 +1,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"; +} |