aboutsummaryrefslogtreecommitdiff
path: root/find_path_graph.cpp
diff options
context:
space:
mode:
authorjack <[email protected]>2024-06-14 13:13:15 -0600
committerjack <[email protected]>2024-06-14 13:13:15 -0600
commitd343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch)
tree96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /find_path_graph.cpp
downloadleetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz
leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip
initial
Diffstat (limited to 'find_path_graph.cpp')
-rw-r--r--find_path_graph.cpp28
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";
+}