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.

---
 .idea/.gitignore                     |  3 +++
 .idea/AlgoGraphJava.iml              | 28 +++++++++++++++++++++
 .idea/codeStyles/Project.xml         |  7 ++++++
 .idea/codeStyles/codeStyleConfig.xml |  5 ++++
 .idea/misc.xml                       |  6 +++++
 .idea/modules.xml                    |  8 ++++++
 .idea/vcs.xml                        |  6 +++++
 src/main/Reachability.java           | 47 ++++++++++++++++++++++++++++++++++++
 src/test/ReachabilityTest.java       | 38 +++++++++++++++++++++++++++++
 9 files changed, 148 insertions(+)
 create mode 100644 .idea/.gitignore
 create mode 100644 .idea/AlgoGraphJava.iml
 create mode 100644 .idea/codeStyles/Project.xml
 create mode 100644 .idea/codeStyles/codeStyleConfig.xml
 create mode 100644 .idea/misc.xml
 create mode 100644 .idea/modules.xml
 create mode 100644 .idea/vcs.xml
 create mode 100644 src/main/Reachability.java
 create mode 100644 src/test/ReachabilityTest.java

diff --git a/.idea/.gitignore b/.idea/.gitignore
new file mode 100644
index 0000000..26d3352
--- /dev/null
+++ b/.idea/.gitignore
@@ -0,0 +1,3 @@
+# Default ignored files
+/shelf/
+/workspace.xml
diff --git a/.idea/AlgoGraphJava.iml b/.idea/AlgoGraphJava.iml
new file mode 100644
index 0000000..f971190
--- /dev/null
+++ b/.idea/AlgoGraphJava.iml
@@ -0,0 +1,28 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<module type="JAVA_MODULE" version="4">
+  <component name="NewModuleRootManager" inherit-compiler-output="true">
+    <exclude-output />
+    <content url="file://$MODULE_DIR$">
+      <sourceFolder url="file://$MODULE_DIR$/src/main" isTestSource="false" />
+      <sourceFolder url="file://$MODULE_DIR$/src/test" isTestSource="true" />
+    </content>
+    <orderEntry type="inheritedJdk" />
+    <orderEntry type="sourceFolder" forTests="false" />
+    <orderEntry type="module-library" scope="TEST">
+      <library name="JUnit5.4">
+        <CLASSES>
+          <root url="jar://$MAVEN_REPOSITORY$/org/junit/jupiter/junit-jupiter/5.4.2/junit-jupiter-5.4.2.jar!/" />
+          <root url="jar://$MAVEN_REPOSITORY$/org/junit/jupiter/junit-jupiter-api/5.4.2/junit-jupiter-api-5.4.2.jar!/" />
+          <root url="jar://$MAVEN_REPOSITORY$/org/apiguardian/apiguardian-api/1.0.0/apiguardian-api-1.0.0.jar!/" />
+          <root url="jar://$MAVEN_REPOSITORY$/org/opentest4j/opentest4j/1.1.1/opentest4j-1.1.1.jar!/" />
+          <root url="jar://$MAVEN_REPOSITORY$/org/junit/platform/junit-platform-commons/1.4.2/junit-platform-commons-1.4.2.jar!/" />
+          <root url="jar://$MAVEN_REPOSITORY$/org/junit/jupiter/junit-jupiter-params/5.4.2/junit-jupiter-params-5.4.2.jar!/" />
+          <root url="jar://$MAVEN_REPOSITORY$/org/junit/jupiter/junit-jupiter-engine/5.4.2/junit-jupiter-engine-5.4.2.jar!/" />
+          <root url="jar://$MAVEN_REPOSITORY$/org/junit/platform/junit-platform-engine/1.4.2/junit-platform-engine-1.4.2.jar!/" />
+        </CLASSES>
+        <JAVADOC />
+        <SOURCES />
+      </library>
+    </orderEntry>
+  </component>
+</module>
\ No newline at end of file
diff --git a/.idea/codeStyles/Project.xml b/.idea/codeStyles/Project.xml
new file mode 100644
index 0000000..919ce1f
--- /dev/null
+++ b/.idea/codeStyles/Project.xml
@@ -0,0 +1,7 @@
+<component name="ProjectCodeStyleConfiguration">
+  <code_scheme name="Project" version="173">
+    <ScalaCodeStyleSettings>
+      <option name="MULTILINE_STRING_CLOSING_QUOTES_ON_NEW_LINE" value="true" />
+    </ScalaCodeStyleSettings>
+  </code_scheme>
+</component>
\ No newline at end of file
diff --git a/.idea/codeStyles/codeStyleConfig.xml b/.idea/codeStyles/codeStyleConfig.xml
new file mode 100644
index 0000000..a55e7a1
--- /dev/null
+++ b/.idea/codeStyles/codeStyleConfig.xml
@@ -0,0 +1,5 @@
+<component name="ProjectCodeStyleConfiguration">
+  <state>
+    <option name="PREFERRED_PROJECT_CODE_STYLE" value="Default" />
+  </state>
+</component>
\ No newline at end of file
diff --git a/.idea/misc.xml b/.idea/misc.xml
new file mode 100644
index 0000000..1763e15
--- /dev/null
+++ b/.idea/misc.xml
@@ -0,0 +1,6 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<project version="4">
+  <component name="ProjectRootManager" version="2" languageLevel="JDK_11" project-jdk-name="11" project-jdk-type="JavaSDK">
+    <output url="file://$PROJECT_DIR$/out" />
+  </component>
+</project>
\ No newline at end of file
diff --git a/.idea/modules.xml b/.idea/modules.xml
new file mode 100644
index 0000000..522549e
--- /dev/null
+++ b/.idea/modules.xml
@@ -0,0 +1,8 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<project version="4">
+  <component name="ProjectModuleManager">
+    <modules>
+      <module fileurl="file://$PROJECT_DIR$/.idea/AlgoGraphJava.iml" filepath="$PROJECT_DIR$/.idea/AlgoGraphJava.iml" />
+    </modules>
+  </component>
+</project>
\ No newline at end of file
diff --git a/.idea/vcs.xml b/.idea/vcs.xml
new file mode 100644
index 0000000..35eb1dd
--- /dev/null
+++ b/.idea/vcs.xml
@@ -0,0 +1,6 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<project version="4">
+  <component name="VcsDirectoryMappings">
+    <mapping directory="" vcs="Git" />
+  </component>
+</project>
\ No newline at end of file
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));
+    }
+}
+
diff --git a/src/test/ReachabilityTest.java b/src/test/ReachabilityTest.java
new file mode 100644
index 0000000..67b29b0
--- /dev/null
+++ b/src/test/ReachabilityTest.java
@@ -0,0 +1,38 @@
+import org.junit.jupiter.api.Test;
+
+import java.util.ArrayList;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+class ReachabilityTest {
+
+    @Test
+    void test() {
+        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
+        for (int i = 0; i < 4; i++) {
+            adj.add(new ArrayList<>());
+        }
+
+        adj.get(0).add(1);
+        adj.get(2).add(1);
+        adj.get(3).add(2);
+        adj.get(0).add(3);
+
+        assertEquals(1, Reachability.reach(adj, 0, 3));
+    }
+
+    @Test
+    void test1() {
+        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
+        for (int i = 0; i < 4; i++) {
+            adj.add(new ArrayList<>());
+        }
+
+        adj.get(0).add(1);
+
+        adj.get(2).add(1);
+
+        assertEquals(0, Reachability.reach(adj, 0, 3));
+    }
+
+}
\ No newline at end of file
-- 
cgit v1.2.3