# Java - Typical 3-color strategy to check if cycle exists - Analysis included

• ``````public class Solution {
/* Three status of nodes:
1. unvisited --> the node has not been touched
2. inProgress  --> the node has been touched, but traversal from it is not finished
3. visited --> the node is clean, which means all descendants have been traversed.
*/
private static final int UNVISTED = 0;
private static final int INPROGRESS = 1;
private static final int VISITED = 2;

//Intuitive way to represent a graph: adjacency list
private void createGraph(int numCourses, List<List<Integer>> nodes, int[][] prerequisites) {
for(int i = 0; i < numCourses; i++) {
}

for(int[] prerequisite : prerequisites) {
}
}

public boolean canFinish(int numCourses, int[][] prerequisites) {
//Step1 : create the graph based on the provided edges.
List<List<Integer>> nodes = new ArrayList<List<Integer>>(numCourses);
createGraph(numCourses, nodes, prerequisites);
int[] status = new int[numCourses];

//Step2 : DFS starting from each node.
for(int i = 0; i < numCourses; i++) {
if(!dfs(i, status, nodes)) {
return false;
}
}

return true;
}

private boolean dfs(int sVertex, int[] status, List<List<Integer>> nodes) {
//Here's the key point of 3-color strategy:
//1. If node is VISITED, then it's clean, all descendants have been traversed.
//2. If INPROGRESS node is traversed again, it means a cycle exists, no topological order exists.
if(status[sVertex] == VISITED) {
return true;
} else if(status[sVertex] == INPROGRESS) {
return false;
}

status[sVertex] = INPROGRESS;

//Traverse all its neighbors
for(int eVertex : nodes.get(sVertex)) {
if(!dfs(eVertex, status, nodes)) {
return false;
}
}

status[sVertex] = VISITED;

return true;
}
}
``````

Time complexity: O(|V| + |E|), every node and edge will be traversed once.

Space complexity: O(|V| + |E|), storing nodes and edges.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.