find cycle

mail@pastecode.io avatar
unknown
plain_text
5 months ago
1.1 kB
1
Indexable
Never
find cycle
package day8_0806;


import java.util.Scanner;

public class find_circle {
	
	static boolean flag;
	static int curNode, node, ed;
	static boolean[] visit;
	static int[][] edges;
	
	private static void check(int idx){
//		visit[]
		for(int i = 0; i < ed; i++){
			if(edges[i][0] == idx && !visit[i]){
				visit[i] = true;
				if(edges[i][1] == curNode){
					flag = true;
					return;
				}
				else check(edges[i][1]);
			}
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int testcase = sc.nextInt();
		for(int tc = 1; tc <= testcase; tc++){
			node = sc.nextInt(); ed = sc.nextInt();
			edges = new int[ed][2];
			for(int i = 0; i < ed; i++){
				edges[i][0] = sc.nextInt();
				edges[i][1] = sc.nextInt();
			}
			
			
			flag = false;
			for(int i = 1; i <= node; i++){
				visit = new boolean[ed];
				curNode = i;
				check(i);
				if(flag) break;
			}
			System.out.println("Case #" + tc);
			if(flag) System.out.println(1);
			else System.out.println(0);
			
		}
	}

}