Untitled
unknown
c_cpp
a year ago
1.4 kB
1
Indexable
Never
// Entry function string cycleDetection(vector<vector<int>>& edges, int n, int m) { bool visited[n+1] = {false}; vector<int> adjList[n+1]; for (auto edge : edges) { // Build adjacency list from given edges info adjList[edge[0]].push_back(edge[1]); adjList[edge[1]].push_back(edge[0]); } for (int i = 1; i <= n; i++) if (!visited[i]) // Consider all disconnected components of a graph. if (cycleDetectUtilBFS(i, visited, adjList)) return "Yes"; return "No"; } bool cycleDetectUtilBFS(int i, bool visited[], vector<int> adjList[]) { queue<pair<int, int> > q; // pair of {node, parent} q.push({i, -1}); while (!q.empty()) { int node = q.front().first; int parent = q.front().second; q.pop(); for (auto connectedNode : adjList[node]) { if (connectedNode != parent) { // while exploring nodes if connectedNode's visited is true // It implies there are more than one ways to reach to the // connectedNode from same source [i], hence cycle exists. if (visited[connectedNode]) return true; else { visited[connectedNode] = true; q.push({connectedNode, node}); } } } } return false; }