2204. Distance to a Cycle in Undirected Graph π
Description
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.
Example 1:
Input: n = 7, edges = [[1,2],[2,4],[4,3],[3,1],[0,1],[5,2],[6,5]] Output: [1,0,0,0,0,1,2] Explanation: 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: n = 9, edges = [[0,1],[1,2],[0,2],[2,6],[6,7],[6,8],[0,3],[3,4],[3,5]] Output: [0,0,0,1,2,2,1,2,2] Explanation: 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.
Solutions
Solution 1: Topological Sorting
We can first convert the edges in $edges$ into an adjacency list $g$, where $g[i]$ represents all adjacent nodes of node $i$, represented as a set.
Next, we delete nodes layer by layer from the outside to the inside until only a cycle remains. The specific method is as follows:
We first find all nodes with a degree of $1$ and remove these nodes from the graph. If after deletion, the degree of its adjacent node becomes $1$, then we add it to the queue $q$. During this process, we record all deleted nodes in order as $seq$; and we use an array $f$ to record the adjacent node of each node that is closer to the cycle, i.e., $f[i]$ represents the adjacent node of node $i$ that is closer to the cycle.
Finally, we initialize an answer array $ans$ of length $n$, where $ans[i]$ represents the minimum distance from node $i$ to any node in the cycle, initially $ans[i] = 0$. Then, we start traversing from the end of $seq$. For each node $i$, we can get the value of $ans[i]$ from its adjacent node $f[i]$, i.e., $ans[i] = ans[f[i]] + 1$.
After the traversal, return the answer array $ans$.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of nodes.
Similar problems:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
|