FindCycle

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


#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;
}

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