From 2dd66619bbd1bf45e092c54f70d89d8f27d269dc Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Sat, 16 May 2020 21:22:14 -0500
Subject: ConnectedComponents (Adding Exits to Maze) done. I didn't build my
 test cases properly initially: when v and w are connected, they should be in
 each other's ArrayList. Once that's fixed, it was easy.

---
 src/main/ConnectedComponents.java     | 44 +++++++++++++++++++++++++++++++++++
 src/test/ConnectedComponentsTest.java | 39 +++++++++++++++++++++++++++++++
 2 files changed, 83 insertions(+)
 create mode 100644 src/main/ConnectedComponents.java
 create mode 100644 src/test/ConnectedComponentsTest.java

(limited to 'src')

diff --git a/src/main/ConnectedComponents.java b/src/main/ConnectedComponents.java
new file mode 100644
index 0000000..915509c
--- /dev/null
+++ b/src/main/ConnectedComponents.java
@@ -0,0 +1,44 @@
+import java.util.ArrayList;
+import java.util.Scanner;
+
+public class ConnectedComponents {
+
+    static int numberOfComponents(ArrayList<ArrayList<Integer>> adj) {
+        ArrayList<Integer> visited = new ArrayList<>();
+        int cc = 0;
+        for (int v = 0; v < adj.size(); v++) {
+            if (!visited.contains(v)) {
+                explore(adj, visited, v);
+                cc++;
+            }
+        }
+        return cc;
+    }
+
+    private static void explore(ArrayList<ArrayList<Integer>> adj, ArrayList<Integer> visited, int v) {
+        visited.add(v);
+
+        for (int n : adj.get(v)) {
+            if (!visited.contains(n))
+                explore(adj, visited, n);
+        }
+    }
+
+    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);
+        }
+        System.out.println(numberOfComponents(adj));
+    }
+}
diff --git a/src/test/ConnectedComponentsTest.java b/src/test/ConnectedComponentsTest.java
new file mode 100644
index 0000000..2e0888c
--- /dev/null
+++ b/src/test/ConnectedComponentsTest.java
@@ -0,0 +1,39 @@
+import org.junit.jupiter.api.Test;
+
+import java.util.ArrayList;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+class ConnectedComponentsTest {
+
+    @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, ConnectedComponents.numberOfComponents(adj));
+    }
+
+    @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(1).add(0);
+        adj.get(2).add(1);
+        adj.get(1).add(2);
+
+        assertEquals(2, ConnectedComponents.numberOfComponents(adj));
+    }
+
+}
\ No newline at end of file
-- 
cgit v1.2.3