Skip to content

Instantly share code, notes, and snippets.

@lordfriend
Created May 12, 2018 16:15
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 lordfriend/65a56eb971f485c00beed0ed0a6412b1 to your computer and use it in GitHub Desktop.
Save lordfriend/65a56eb971f485c00beed0ed0a6412b1 to your computer and use it in GitHub Desktop.
Find a cycle in directed graph
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Stack;
public class Acyclicity {
private static int acyclic(ArrayList<Integer>[] adj) {
//write your code here
boolean[] visited = new boolean[adj.length];
Stack<Integer> vStack = new Stack<>();
for (int v = 0; v < adj.length; v++) {
if (visited[v]) {
continue;
}
visited[v] = true;
vStack.push(v);
while(!vStack.isEmpty()) {
int x = vStack.pop();
for (Integer u: adj[x]) {
if (u == v) {
return 1;
}
if (visited[u]) {
continue;
}
visited[u] = true;
vStack.push(u);
}
}
}
return 0;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
ArrayList<Integer>[] adj = (ArrayList<Integer>[])new ArrayList[n];
for (int i = 0; i < n; i++) {
adj[i] = new ArrayList<Integer>();
}
for (int i = 0; i < m; i++) {
int x, y;
x = scanner.nextInt();
y = scanner.nextInt();
adj[x - 1].add(y - 1);
}
System.out.println(acyclic(adj));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment