Find Cycle

Level 3
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
0


Case #1
1
Case #2
0
Case #3
0
Case #4
0
Case #5
1
Case #6
1
Case #7
0

7
3 3
1 2
2 3
3 1
3 2
1 2
1 3
4 3 
1 2
2 3
1 4
4 3
2 3
3 4
3 1
5 5
2 3
3 4
4 5
5 3
3 1
4 4
1 2
2 3
3 4
4 2
4 4
1 2
2 3
3 4
1 4

#include <iostream>
using namespace std;

int T, n, m;
bool result;
int mp[1001][1001], cnt[1001];
bool vs[1001];

void resetVs(){
	for(int i = 1; i <= n; i++) vs[i] = false;
}

void dfs(int index){
	if(result){
		return;
	}
	for(int i = 1; i <= n; i++){
		if(mp[index][i] && vs[i]){
			result = true;
			break;
		} else if(mp[index][i] && !vs[i]){
			vs[i] = true;
			dfs(i);
			vs[i] = false;
		}
	}
}

int main(){
	freopen("input.txt", "r", stdin);
	cin >> T;

	for(int tc = 1; tc <= T; tc++){
		// Input
		cin >> n >> m;
		int a, b;
		for(int i = 1; i <= n; i++){
			cnt[i] = 0;
			for(int j = 1; j <= n; j++) mp[i][j] = 0;
		}
		for(int i = 0; i < m; i++){
			cin >> a >> b;
			mp[a][b] = 1;
			cnt[a]++;
		}

		// Initial
		result = false;

		// Solve Problem
		for(int i = 1; i <= n; i++){
			if(result) break;
			if(cnt[i]){
				//resetVs();
				vs[i] = true;
				dfs(i);
				vs[i] = false;
			}
		}

		// Output
		cout << "Case #" << tc << endl << (result ? 1 : 0) << endl;
	}

	return 0;
 }