# Find cycle

ptrdung
c_cpp
22 days ago
1.6 kB
0
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
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
*/
// code ngu lon
#include <iostream>

using namespace std;

int node, edge;
int mattrix[30][30];
int stack[900], top;
int flag;
int visited[30];
int T;
// tim chu trinh bat dau tu start
void cycle(int start, int current)
{
if(flag == 1) return;
if(flag == 0)
{
for(int i = 1; i <= node; i++)
{
if(mattrix[current][i] == 1)
{
if(i == start)
{
flag  = 1;
return ;
}else {if(visited[i] == 0) {visited[i] = 1; cycle(start, i); visited[i] = 0;}}

}
}
}
}

int main()
{
//freopen("input1.txt", "r", stdin);
cin >> T;
for(int tc = 1; tc <= T; tc++)
{
cin >> node >> edge;
for(int i = 1; i <= node; i++)
{

for(int j = 1; j <= node; j++)
mattrix[i][j] = 0;
}
for(int i = 1; i <= edge; i++)
{
int x, y;
cin >> x >> y;
mattrix[x][y] = 1;
}
flag = 0;
for(int i = 1; i <= node; i++)
{
if(flag == 1) break;
visited[i] = 1;
cycle(i, i);
visited[i] = 0;
}
cout << "Case #" << tc << endl << flag << endl;
}
return 0;
}```