2204. Distance to a Cycle in Undirected Graph

You are given a positive integer n representing the number of nodes in a connected undirected graph containing exactly one cycle. The nodes are numbered from 0 to n - 1 (inclusive).

You are also given a 2D integer array edges, where edges[i] = [node1i, node2i] denotes that there is a bidirectional edge connecting node1i and node2i in the graph.

The distance between two nodes a and b is defined to be the minimum number of edges that are needed to go from a to b.

Return an integer array answer of size n, where answer[i] is the minimum distance between the ith node and any node in the cycle.

class Solution {
    vector<vector<int>> g;
    vector<pair<int,int>> st;
    vector<vector<pair<int,int>>> bcc;
    vector<int> vis, mi;
    int rep = 1;
    
    void BCC(int u, int p) {
        vis[u] = mi[u] = rep++;
        for(auto& v : g[u]) {
            if(v == p) continue;
            if(vis[u] > vis[v]) {
                st.push_back({u,v});
            }
            if(vis[v]) {
                mi[u] = min(mi[u], vis[v]);
            } else {
                BCC(v,u);
                mi[u] = min(mi[u], mi[v]);
                if(mi[v] >= vis[u]) {
                    bcc.emplace_back();
                    while(!st.empty()) {
                        auto conn = st.back(); st.pop_back();
                        bcc.back().push_back(conn);
                        if(conn.first == u and conn.second == v) break;
                    }
                }
            }
        }
    }
public:
    vector<int> distanceToCycle(int n, vector<vector<int>>& edges) {
        g = vector<vector<int>>(n);
        vis = vector<int>(n);
        mi = vector<int>(n);
        for(auto& e : edges) {
            g[e[0]].push_back(e[1]);
            g[e[1]].push_back(e[0]);
        }
        BCC(0,-1);
        
        vector<int> res(n,-1);
        queue<int> q;
        for(auto& components : bcc) {
            if(components.size() > 1) {
                for(auto [u, v] : components) {
                    if(res[u] == -1) {
                        res[u] = 0; q.push(u);
                    }
                    if(res[v] == -1) {
                        res[v] = 0; q.push(v);
                    }
                }
            }
        }
        
        while(!q.empty()) {
            auto u = q.front(); q.pop();
            for(auto v : g[u]) {
                if(res[v] == -1) {
                    res[v] = res[u] + 1;
                    q.push(v);
                }
            }
        }
        
        return res;
    }
};