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; }
Leave a Comment