Skip to content

Instantly share code, notes, and snippets.

@HauptJ
Created February 12, 2020 03:23
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save HauptJ/6d17cedb2cc67e2661ec850edece70a5 to your computer and use it in GitHub Desktop.
Save HauptJ/6d17cedb2cc67e2661ec850edece70a5 to your computer and use it in GitHub Desktop.
class Solution {
static int WHITE = 0, GRAY = 1, BLACK = 2;
private int V;
private LinkedList<Integer> adj[];
Graph(int v) {
V = v;
adj = new LinkedList[v];
for(int i = 0; i < v; ++i)
adj[i] = new LinkedList();
}
//Function to add an edge into the graph
void addEdge(int v, int w){
adj[v].add(w); // Add w to v's list
}
// Find if there is a back edge in DFS graph rooted with v
int[] DFSUtil(int v, int[] color){
// Vertex being processed
color[v] = GRAY;
// Iterate through all adjacent vertices
Iterator<Integer> i = adj[v].listIterator();
while (i.hasNext()){
int n = i.next()
// If the current vertex is already grey (visited)
if(color[n] == GRAY){
System.out.print("Cycle at: " + n);
return null;
}
// If v is not processed and there is a back edge in the graph
if(color[n]== WHITE && DFSUtil(n color) == null ){
return null;
}
}
// Mark the vertex as processed (black)
color[v] = BLACK;
return color;
}
int[] DFS(int v){
// Initialize all vertices to WHITE
int[] color = new int[V]
for(int i = 0; i < V; i++){
color[i] = WHITE;
}
// Perform a DFS with all vertices
DFSUtil(v, color)
}
}
public int[] findOrder(int numCourses, int[][] prerequisites) {
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment