Untitled

unknown
plain_text
5 months ago
1.6 kB
4
Indexable
Never
```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);

}
}

}```