summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorHaidong Ji2020-05-20 18:37:36 -0500
committerHaidong Ji2020-05-20 18:37:36 -0500
commita3d28d9ea91f90af072066b2a77030e929ab0f0e (patch)
treebe4ae5b824f003f1050590415043f685ad13f564 /src
parent2dd66619bbd1bf45e092c54f70d89d8f27d269dc (diff)
Check if DAG (Directed Acyclic Graph) done. In the exercise it's Checking Consistency of CS Curriculum. For the clock variable to assign pre-visit and post-visit values, I used a trick of defining the clock as int[1], so its mutable and I can increment it. I don't know if that's a best practice, but for now I'm happy that the program is good. Fun stuff!
Diffstat (limited to 'src')
-rw-r--r--src/main/Acyclicity.java59
-rw-r--r--src/test/AcyclicityTest.java55
2 files changed, 114 insertions, 0 deletions
diff --git a/src/main/Acyclicity.java b/src/main/Acyclicity.java
new file mode 100644
index 0000000..1d69ab8
--- /dev/null
+++ b/src/main/Acyclicity.java
@@ -0,0 +1,59 @@
+import java.util.ArrayList;
+import java.util.Scanner;
+
+public class Acyclicity {
+ static int acyclic(ArrayList<ArrayList<Integer>> adj) {
+ ArrayList<Integer> visited = new ArrayList<>();
+ int[] prev = new int[adj.size()];
+ int[] postv = new int[adj.size()];
+ int[] clock = new int[1];
+ clock[0] = 0;
+ dfs(adj, visited, prev, postv, clock);
+
+ for (int u = 0; u < adj.size(); u++) {
+ for (int v : adj.get(u)) {
+ if (postv[u] <= postv[v])
+ return 1;
+ }
+ }
+ return 0;
+ }
+
+ private static void dfs(ArrayList<ArrayList<Integer>> adj, ArrayList<Integer> visited, int[] prev, int[] postv, int[] clock) {
+ for (int v = 0; v < adj.size(); v++) {
+ if (!visited.contains(v))
+ explore(adj, v, visited, prev, postv, clock);
+ }
+ }
+
+ private static void explore(ArrayList<ArrayList<Integer>> adj, int v, ArrayList<Integer> visited, int[] prev, int[] postv, int[] clock) {
+ visited.add(v);
+ prev[v] = clock[0];
+ clock[0] = clock[0] + 1;
+
+ for (int n : adj.get(v)) {
+ if (!visited.contains(n))
+ explore(adj, n, visited, prev, postv, clock);
+ }
+ postv[v] = clock[0];
+ clock[0] = clock[0] + 1;
+
+ }
+
+ 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);
+ }
+ System.out.println(acyclic(adj));
+ }
+}
diff --git a/src/test/AcyclicityTest.java b/src/test/AcyclicityTest.java
new file mode 100644
index 0000000..9d67894
--- /dev/null
+++ b/src/test/AcyclicityTest.java
@@ -0,0 +1,55 @@
+import org.junit.jupiter.api.Test;
+
+import java.util.ArrayList;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+class AcyclicityTest {
+
+ @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(3).add(0);
+ adj.get(1).add(2);
+ adj.get(2).add(0);
+
+ assertEquals(1, Acyclicity.acyclic(adj));
+ }
+
+ @Test
+ void test1() {
+ ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
+ for (int i = 0; i < 5; i++) {
+ adj.add(new ArrayList<>());
+ }
+
+ adj.get(0).add(1);
+ adj.get(1).add(2);
+ adj.get(0).add(2);
+ adj.get(2).add(3);
+ adj.get(0).add(3);
+ adj.get(1).add(4);
+ adj.get(2).add(4);
+
+ assertEquals(0, Acyclicity.acyclic(adj));
+ }
+
+ @Test
+ void test2() {
+ 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);
+
+ assertEquals(0, Acyclicity.acyclic(adj));
+ }
+} \ No newline at end of file