Untitled
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...