判断有向图图是否有环_判断有向图是否有环,若有环,则将环剔除java

package Graph;
 
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Stack;
 
public class DirectedCycle {
	int v, e;
	boolean []visit;
	boolean []onStack;
	int []path;
	boolean hasCycle = false;
	int s;
	Stack<Integer> stack;
	LinkedList<Integer> []adj;
	public static void main(String[] args) {
		new DirectedCycle().run();
	}
	public void run() {
		Scanner in = new Scanner(System.in);
		v = in.nextInt();
		e = in.nextInt();
		visit = new boolean[v+1];
		onStack = new boolean[v+1];
		adj = new LinkedList[v+1];
		path = new int[v];
		stack = new Stack<>();
		for(int i = 0; i < v; i++ ) {
			adj[i] = new LinkedList<>();
		}
		for(int i = 0; i < e; i++ ) {
			int a = in.nextInt();
			int b = in.nextInt();
			adj[a].offer(b);
		}
		for(int i = 0; i < v; i++ ) {
			if(!visit[i])
				dfs(i);
		}
		if(hasCycle)
			printPath();
		else {
			System.out.println("No cycle!");
		}
	}
	public void printPath() {
		boolean flag = true;
		while(!stack.isEmpty()) {
			if(flag) {
				System.out.print(stack.pop());
				flag = false;
			}
			else
				System.out.print("-" + stack.pop());
		}
	}
	public void dfs(int cur) {
		visit[cur] = true;
		onStack[cur] = true;
		for(int w :adj[cur]) {
			if(!visit[w]) {
				path[w] = cur;
				dfs(w);
			}
			else if(onStack[w]) {
				hasCycle = true;
				stack.push(cur);//把结束点多入栈一次标记结束位置以区别与其他环
				for(int x = cur; x != w; x = path[x])//结束点为当前第一个出现的已标记并且在栈内的点
					stack.push(x);
				stack.push(w);
					return;
			}
		}
		onStack[cur] = false;
	}
	
	
	
	
 
}