Find cycle
ptrdung
c_cpp
a year ago
1.6 kB
7
Indexable
/* 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; }
Editor is loading...
Leave a Comment