Distance to a Cycle in Undirected Graph

3 min readUpdated 23 May 2025

Problem Statement

In this problem, you are provided with an integer n indicating the number of nodes in a connected undirected graph that contains exactly one cycle. Each node in this graph is uniquely numbered from 0 to n-1. Additionally, you are given an array edges where each entry edges[i] contains a pair [node1i, node2i] showing that there is a bidirectional edge connecting the nodes node1i and node2i.

The task is to determine the minimum number of edges required to travel from each node i to any node that is part of the cycle. Your solution should return this information in the form of an array answer of size n, where answer[i] represents the minimum distance from node i to the nearest node in the cycle.

Examples

Example 1

Input:

EXAMPLE_ENTITY

n = 7, edges = [[1,2],[2,4],[4,3],[3,1],[0,1],[5,2],[6,5]]

Output:

EXAMPLE_ENTITY

[1,0,0,0,0,1,2]

Explanation:

EXAMPLE_ENTITY

The nodes 1, 2, 3, and 4 form the cycle.
The distance from 0 to 1 is 1.
The distance from 1 to 1 is 0.
The distance from 2 to 2 is 0.
The distance from 3 to 3 is 0.
The distance from 4 to 4 is 0.
The distance from 5 to 2 is 1.
The distance from 6 to 2 is 2.

Example 2

Input:

EXAMPLE_ENTITY

n = 9, edges = [[0,1],[1,2],[0,2],[2,6],[6,7],[6,8],[0,3],[3,4],[3,5]]

Output:

EXAMPLE_ENTITY

[0,0,0,1,2,2,1,2,2]

Explanation:

EXAMPLE_ENTITY

The nodes 0, 1, and 2 form the cycle.
The distance from 0 to 0 is 0.
The distance from 1 to 1 is 0.
The distance from 2 to 2 is 0.
The distance from 3 to 1 is 1.
The distance from 4 to 1 is 2.
The distance from 5 to 1 is 2.
The distance from 6 to 2 is 1.
The distance from 7 to 2 is 2.
The distance from 8 to 2 is 2.

Constraints

3 <= n <= 105
edges.length == n
edges[i].length == 2
0 <= node1i, node2i <= n - 1
node1i != node2i
The graph is connected.
The graph has exactly one cycle.
There is at most one edge between any pair of vertices.

Approach and Intuition

Given the nature of the problem—finding distances in a graph with exactly one cycle—the plan involves several distinct steps to arrive at the solution:

Identify the Cycle: Since the graph is guaranteed to have exactly one cycle and no node is isolated due to the graph being connected, we can use a Depth First Search (DFS) or Breadth-First Search (BFS) to locate this cycle. During the traversal, if a node is reached that is already visited and is not the parent of the current node, a cycle is detected.
Calculate Cycle Distances: Upon detection of the cycle, we can mark all nodes that are part of the cycle. The distance of these nodes to themselves (as part of the cycle) is 0.
Propagate Minimum Distances: Starting from each node identified as part of the cycle, perform a breadth-first search to propagate the distance to all other nodes. The BFS ensures that the shortest path in an unweighted graph (like ours, where each edge has the same weight) is found from the cycle nodes to all other nodes.
Output the Solution: Collect and return the distances calculated as an array, where each index corresponds to the respective node and the value at that index represents the minimum distance to the cycle.

This method is efficient due to the linear relationship between nodes and edges (given by n and n in constraints) and the use of BFS, which is well-suited for shortest-path calculations in unweighted graphs. By identifying the cycle first and then spreading out to calculate distances, the approach directly addresses the problem's requirements while adhering to the constraints provided.

Solutions

CPP
class Solution {
public:
    vector<int> findDistances(int nodesCount, vector<vector<int>>& connections) {
        vector<bool> partOfCycle(nodesCount, true),
            expanded(nodesCount, false); // Initial states for all nodes
        vector<int> connectivity(nodesCount, 0), resultDistances(nodesCount);
        vector<vector<int>> links(nodesCount, vector<int>());
    
        // Create a list of links and calculate degrees of connectivity
        for (auto connection : connections) {
            links[connection[0]].push_back(connection[1]);
            links[connection[1]].push_back(connection[0]);
            connectivity[connection[0]]++;
            connectivity[connection[1]]++;
        }
    
        queue<int> processingQueue;
    
        // Identify all external nodes (degree 1)
        for (int node = 0; node < nodesCount; node++) {
            if (connectivity[node] == 1) {
                processingQueue.push(node);
            }
        }
    
        // BFS to identify cycle nodes by removing nodes with single connections
        while (!processingQueue.empty()) {
            int currentNode = processingQueue.front();
            processingQueue.pop();
            partOfCycle[currentNode] = false; // Node is not part of any cycle
    
            // Decrement the degree of nodes connected to current and enqueue if isolated
            for (auto adjacent : links[currentNode]) {
                connectivity[adjacent]--;
                if (connectivity[adjacent] == 1) {
                    processingQueue.push(adjacent);
                }
            }
        }
    
        // Queue cycle nodes for distance calculations
        for (int node = 0; node < nodesCount; node++) {
            if (partOfCycle[node]) {
                processingQueue.push(node);
                expanded[node] = true;
            }
        }
    
        // Use BFS to calculate distances from the nodes in cycles
        int layerDistance = 0;
        while (!processingQueue.empty()) {
            int layerSize = processingQueue.size(); // Number of nodes at current layer
            for (int i = 0; i < layerSize; i++) {
                int currentNode = processingQueue.front();
                processingQueue.pop();
                    
                resultDistances[currentNode] = layerDistance; // Set distance for nodes
                    
                // Enqueue neighboring nodes for next layer, avoid returning to previous
                for (auto neighbor : links[currentNode]) {
                    if (expanded[neighbor]) continue;
                    processingQueue.push(neighbor);
                    expanded[neighbor] = true;
                }
            }
            layerDistance++; // Increase the distance for the next layer of BFS
        }
    
        return resultDistances;
    }
};
Powered by Vultr AgentBeta

The described C++ solution implements the calculation of the shortest distance from each node to a cycle within an undirected graph. It comprises an intricate algorithm combining aspects of graph theory, specifically Breadth First Search (BFS), and a queueing mechanism for processing nodes.

The solution class contains a single function, findDistances(), that takes two parameters: nodesCount which represents the total number of nodes in the graph, and connections, a 2D vector where each subvector represents a bidirectional edge between two nodes.

In executing this function, the following steps take place:

Initialize various vectors to manage the state and connectivity of nodes, such as partOfCycle which identifies whether a node is part of a cycle or not, expanded to know if a node has been expanded in BFS, connectivity to manage connection degrees, and links to store adjacency lists for each node.
Utilize the connections input to populate the links vector and calculate the degree of connectivity for each node. This preparation allows for a more efficient operation during the BFS process.
Identify all external nodes that have only one connection and push them onto a processingQueue, thereby setting up the initial state of BFS.
Execute a BFS process to probe and identify all nodes that are part of a cycle by effectively ‘peeling’ the graph's outer layers, affecting nodes with a single connection repeatedly. This reduction continues until only cyclic or interconnected nodes remain.
For nodes determined to be part of a cycle, reinitialize and prepare the processingQueue and expanded state array to calculate the distances using another BFS iteration.
During the distance calculation BFS, iterate over each node layer by layer, increasing the layerDistance progressively to ensure correct distance measurement from cycle nodes to non-cycle nodes. This BFS segregates distance tracking by processing only non-expanded neighboring nodes, thus ensuring efficiency and accuracy by avoiding repeat calculations.
Return the resultant distances for each node, encapsulated in the resultDistances vector which provides a direct distance measure from every node to the nearest cycle in the graph.

This solution is comprehensive and efficiently handles the complexity of determining node distances in relation to graph cycles, leveraging BFS and effective queue management.

0 Comments

Start the conversation

Be the first to comment and share your perspective with the community.

Distance to a Cycle in Undirected Graph

3 min readUpdated 23 May 2025

Problem Statement

Examples

Example 1

Input:

EXAMPLE_ENTITY

n = 7, edges = [[1,2],[2,4],[4,3],[3,1],[0,1],[5,2],[6,5]]

Output:

EXAMPLE_ENTITY

[1,0,0,0,0,1,2]

Explanation:

EXAMPLE_ENTITY

The nodes 1, 2, 3, and 4 form the cycle.
The distance from 0 to 1 is 1.
The distance from 1 to 1 is 0.
The distance from 2 to 2 is 0.
The distance from 3 to 3 is 0.
The distance from 4 to 4 is 0.
The distance from 5 to 2 is 1.
The distance from 6 to 2 is 2.

Example 2

Input:

EXAMPLE_ENTITY

n = 9, edges = [[0,1],[1,2],[0,2],[2,6],[6,7],[6,8],[0,3],[3,4],[3,5]]

Output:

EXAMPLE_ENTITY

[0,0,0,1,2,2,1,2,2]

Explanation:

EXAMPLE_ENTITY

The nodes 0, 1, and 2 form the cycle.
The distance from 0 to 0 is 0.
The distance from 1 to 1 is 0.
The distance from 2 to 2 is 0.
The distance from 3 to 1 is 1.
The distance from 4 to 1 is 2.
The distance from 5 to 1 is 2.
The distance from 6 to 2 is 1.
The distance from 7 to 2 is 2.
The distance from 8 to 2 is 2.

Constraints

3 <= n <= 105
edges.length == n
edges[i].length == 2
0 <= node1i, node2i <= n - 1
node1i != node2i
The graph is connected.
The graph has exactly one cycle.
There is at most one edge between any pair of vertices.

Approach and Intuition

Given the nature of the problem—finding distances in a graph with exactly one cycle—the plan involves several distinct steps to arrive at the solution:

Identify the Cycle: Since the graph is guaranteed to have exactly one cycle and no node is isolated due to the graph being connected, we can use a Depth First Search (DFS) or Breadth-First Search (BFS) to locate this cycle. During the traversal, if a node is reached that is already visited and is not the parent of the current node, a cycle is detected.
Calculate Cycle Distances: Upon detection of the cycle, we can mark all nodes that are part of the cycle. The distance of these nodes to themselves (as part of the cycle) is 0.
Propagate Minimum Distances: Starting from each node identified as part of the cycle, perform a breadth-first search to propagate the distance to all other nodes. The BFS ensures that the shortest path in an unweighted graph (like ours, where each edge has the same weight) is found from the cycle nodes to all other nodes.
Output the Solution: Collect and return the distances calculated as an array, where each index corresponds to the respective node and the value at that index represents the minimum distance to the cycle.

Solutions

CPP
class Solution {
public:
    vector<int> findDistances(int nodesCount, vector<vector<int>>& connections) {
        vector<bool> partOfCycle(nodesCount, true),
            expanded(nodesCount, false); // Initial states for all nodes
        vector<int> connectivity(nodesCount, 0), resultDistances(nodesCount);
        vector<vector<int>> links(nodesCount, vector<int>());
    
        // Create a list of links and calculate degrees of connectivity
        for (auto connection : connections) {
            links[connection[0]].push_back(connection[1]);
            links[connection[1]].push_back(connection[0]);
            connectivity[connection[0]]++;
            connectivity[connection[1]]++;
        }
    
        queue<int> processingQueue;
    
        // Identify all external nodes (degree 1)
        for (int node = 0; node < nodesCount; node++) {
            if (connectivity[node] == 1) {
                processingQueue.push(node);
            }
        }
    
        // BFS to identify cycle nodes by removing nodes with single connections
        while (!processingQueue.empty()) {
            int currentNode = processingQueue.front();
            processingQueue.pop();
            partOfCycle[currentNode] = false; // Node is not part of any cycle
    
            // Decrement the degree of nodes connected to current and enqueue if isolated
            for (auto adjacent : links[currentNode]) {
                connectivity[adjacent]--;
                if (connectivity[adjacent] == 1) {
                    processingQueue.push(adjacent);
                }
            }
        }
    
        // Queue cycle nodes for distance calculations
        for (int node = 0; node < nodesCount; node++) {
            if (partOfCycle[node]) {
                processingQueue.push(node);
                expanded[node] = true;
            }
        }
    
        // Use BFS to calculate distances from the nodes in cycles
        int layerDistance = 0;
        while (!processingQueue.empty()) {
            int layerSize = processingQueue.size(); // Number of nodes at current layer
            for (int i = 0; i < layerSize; i++) {
                int currentNode = processingQueue.front();
                processingQueue.pop();
                    
                resultDistances[currentNode] = layerDistance; // Set distance for nodes
                    
                // Enqueue neighboring nodes for next layer, avoid returning to previous
                for (auto neighbor : links[currentNode]) {
                    if (expanded[neighbor]) continue;
                    processingQueue.push(neighbor);
                    expanded[neighbor] = true;
                }
            }
            layerDistance++; // Increase the distance for the next layer of BFS
        }
    
        return resultDistances;
    }
};
Powered by Vultr AgentBeta

The solution class contains a single function, findDistances(), that takes two parameters: nodesCount which represents the total number of nodes in the graph, and connections, a 2D vector where each subvector represents a bidirectional edge between two nodes.

In executing this function, the following steps take place:

Initialize various vectors to manage the state and connectivity of nodes, such as partOfCycle which identifies whether a node is part of a cycle or not, expanded to know if a node has been expanded in BFS, connectivity to manage connection degrees, and links to store adjacency lists for each node.
Utilize the connections input to populate the links vector and calculate the degree of connectivity for each node. This preparation allows for a more efficient operation during the BFS process.
Identify all external nodes that have only one connection and push them onto a processingQueue, thereby setting up the initial state of BFS.
Execute a BFS process to probe and identify all nodes that are part of a cycle by effectively ‘peeling’ the graph's outer layers, affecting nodes with a single connection repeatedly. This reduction continues until only cyclic or interconnected nodes remain.
For nodes determined to be part of a cycle, reinitialize and prepare the processingQueue and expanded state array to calculate the distances using another BFS iteration.
During the distance calculation BFS, iterate over each node layer by layer, increasing the layerDistance progressively to ensure correct distance measurement from cycle nodes to non-cycle nodes. This BFS segregates distance tracking by processing only non-expanded neighboring nodes, thus ensuring efficiency and accuracy by avoiding repeat calculations.
Return the resultant distances for each node, encapsulated in the resultDistances vector which provides a direct distance measure from every node to the nearest cycle in the graph.

This solution is comprehensive and efficiently handles the complexity of determining node distances in relation to graph cycles, leveraging BFS and effective queue management.

0 Comments

Start the conversation

Be the first to comment and share your perspective with the community.