summaryrefslogtreecommitdiff
path: root/src/main
diff options
context:
space:
mode:
Diffstat (limited to 'src/main')
-rw-r--r--src/main/Reachability.java47
1 files changed, 47 insertions, 0 deletions
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));
+ }
+}
+