# Find Cycle

quoc14
c_cpp
16 days ago
1.8 kB
3
Indexable
Never
DFS and BFS
```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;
}```