diff options
| -rw-r--r-- | .idea/.gitignore | 3 | ||||
| -rw-r--r-- | .idea/AlgoGraphJava.iml | 28 | ||||
| -rw-r--r-- | .idea/codeStyles/Project.xml | 7 | ||||
| -rw-r--r-- | .idea/codeStyles/codeStyleConfig.xml | 5 | ||||
| -rw-r--r-- | .idea/misc.xml | 6 | ||||
| -rw-r--r-- | .idea/modules.xml | 8 | ||||
| -rw-r--r-- | .idea/vcs.xml | 6 | ||||
| -rw-r--r-- | src/main/Reachability.java | 47 | ||||
| -rw-r--r-- | src/test/ReachabilityTest.java | 38 |
9 files changed, 148 insertions, 0 deletions
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 |