Untitled

mail@pastecode.io avatar
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;
}