From bc5a6815181068e76316aa4a611647124d18ba48 Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Sun, 10 May 2020 16:18:46 -0500
Subject: Reachability done. I found it much easier to work with Java than
 Python. I tried to start with Python but found it difficult to get started.

---
 src/main/Reachability.java | 47 ++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 47 insertions(+)
 create mode 100644 src/main/Reachability.java

(limited to 'src/main')

diff --git a/src/main/Reachability.java b/src/main/Reachability.java
new file mode 100644
index 0000000..8d6ab78
--- /dev/null
+++ b/src/main/Reachability.java
@@ -0,0 +1,47 @@
+import java.util.ArrayList;
+import java.util.Scanner;
+
+public class Reachability {
+
+    static int reach(ArrayList<ArrayList<Integer>> adj, int x, int y) {
+        ArrayList<Integer> visited = new ArrayList<>();
+        if (x == y)
+            return 1;
+        explore(adj, visited, x, y);
+        if (visited.contains(y))
+            return 1;
+        return 0;
+    }
+
+    private static void explore(ArrayList<ArrayList<Integer>> adj, ArrayList<Integer> visited, int x, int y) {
+        visited.add(x);
+        if (x == y)
+            return;
+        for (int n : adj.get(x)) {
+            if (!visited.contains(n))
+                explore(adj, visited, n, y);
+        }
+    }
+
+
+    public static void main(String[] args) {
+        Scanner scanner = new Scanner(System.in);
+        int n = scanner.nextInt();
+        int m = scanner.nextInt();
+        ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>();
+        for (int i = 0; i < n; i++) {
+            adj.add(new ArrayList<Integer>());
+        }
+        for (int i = 0; i < m; i++) {
+            int x, y;
+            x = scanner.nextInt();
+            y = scanner.nextInt();
+            adj.get(x - 1).add(y - 1);
+            adj.get(y - 1).add(x - 1);
+        }
+        int x = scanner.nextInt() - 1;
+        int y = scanner.nextInt() - 1;
+        System.out.println(reach(adj, x, y));
+    }
+}
+
-- 
cgit v1.2.3