Untitled

 avatar
unknown
plain_text
2 years ago
1.6 kB
7
Indexable
Find cycle



Given a directed graph, check whether the graph contains a cycle or not. Your function should return 1 if the given graph contains at least one cycle, else return 0. 
 
Input
-------------------------
3   --> total TC count
3 3    --> TC 1 input number of nodes and number of edges
1 2
2 3
3 1
3 2   --> TC 2 input
1 2
1 3
4 3    --> ... 
1 2
2 3
1 4 
 
Output
--------------------------------
Case #1
1
Case #2
0
Case #3




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);
			
		}
	}

}
Editor is loading...