Untitled
unknown
c_cpp
2 years ago
1.4 kB
5
Indexable
////////////////////// APPROACH - 1 (DFS) int detectCycleInDirectedGraphApproach1(int n, vector < pair < int, int >> & edges) { vector<int> adjList[n+1]; for (auto edge : edges) { adjList[edge.first].push_back(edge.second); } // 0 -> unvisited, 1 -> visited, 2 -> DfsVisited // visited -> node has been visited but its not in current dfs call hierarchy. // DfsVisited -> node has been visited and is in current dfs call hierarchy. int visited[n+1] = {0}; for (int i = 1; i <= n; i++) { if (visited[i] == 0) // check for cycle from unvisited nodes if (detectCycle(i, adjList, visited)) return true; } return false; } bool detectCycle(int node, vector<int> adjList[], int visited[]) { // if node is DfsVisited, cycle exists. // Note if visited[node] == 1, then cycle doesn’t exist bcz the node is not in current // dfs call hierarchy. if (visited[node] == 2) return true; // made node DfsVisited, i.e. node is in current dfs call hierarchy visited[node] = 2; for (int j = 0; j < adjList[node].size(); j++) { if (detectCycle(adjList[node][j], adjList, visited)) return true; } // make node visited, i.e. it has been visited while traversing, but now its not in // current dfs call hierarchy. visited[node] = 1; return false; }
Editor is loading...