java 解法, 执行用时: 19 ms, 内存消耗: 100.9 MB, 提交时间: 2023-10-21 19:40:23

class Solution {
    public int[] distanceToCycle(int n, int[][] edges) {
        // 首先用拓扑排序寻找环
        int[] degree = new int[n];
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++)
            graph.add(new ArrayList<>());
        for (int[] o : edges) {
            graph.get(o[0]).add(o[1]);
            graph.get(o[1]).add(o[0]);
            degree[o[0]]++;
            degree[o[1]]++;
        }
        Queue<Integer> queue = new LinkedList<>();
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            // 因为给的是无向图，应该以度为 1 的点为起点做拓扑排序
            if (degree[i] == 1) {
                degree[i]--;
                queue.offer(i);
            }
        }
        // 如果没有度为 1 的起点被加入队列，说明整个图就是一个环
        if (queue.size() == 0) {
            Arrays.fill(res, 0);
            return res;
        }
        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int v : graph.get(u)) {
                degree[v]--;
                // 如果度变为 1 则加入队列
                if (degree[v] == 1)
                    queue.offer(v);
            }
        }
        // 用 Integer.MAX_VALUE 标记未访问的节点
        Arrays.fill(res, Integer.MAX_VALUE);
        for (int i = 0; i < n; i++) {
            // 拓扑排序后度依然为 2 的点就是环中的点（注意到有且只有一个环），将它们入队
            if (degree[i] == 2) {
                queue.offer(i);
                res[i] = 0;
            }
        }
        // 广度优先搜索为所有节点赋值
        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int v : graph.get(u)) {
                if (res[v] == Integer.MAX_VALUE)
                    queue.offer(v);
                res[v] = Math.min(res[v], res[u] + 1);
            }
        }
        return res;
    }
}

python3 解法, 执行用时: 356 ms, 内存消耗: 171.7 MB, 提交时间: 2023-10-21 19:39:57

from collections import defaultdict, deque
from typing import DefaultDict, List, Set

class Solution:
    def distanceToCycle(self, n: int, edges: List[List[int]]) -> List[int]:
        def findCycle(n: int, adjMap: DefaultDict[int, Set[int]]) -> List[int]:
            def dfs(cur: int, pre: int) -> bool:
                """环检测，并记录路径"""
                if visited[cur]:
                    return True
                visited[cur] = True
                for next in adjMap[cur]:
                    if next == pre:
                        continue
                    path.append(next)
                    if dfs(next, cur):
                        return True
                    path.pop()
                return False

            res = []
            path = []
            visited = [False] * n

            for i in range(n):
                if visited[i]:
                    continue
                path = [i]
                if dfs(i, -1):
                    break

            last = path.pop()
            res.append(last)
            while path and path[-1] != last:
                res.append(path.pop())

            return res

        """无向图中恰有一个环"""
        adjMap = defaultdict(set)
        for u, v in edges:
            adjMap[u].add(v)
            adjMap[v].add(u)

        cycle = findCycle(n, adjMap)

        res = [int(1e20)] * n
        for index in cycle:
            res[index] = 0

        queue = deque([i for i in cycle])
        dist = 0
        while queue:
            length = len(queue)
            for _ in range(length):
                cur = queue.popleft()
                for next in adjMap[cur]:
                    if res[next] > dist + 1:
                        res[next] = dist + 1
                        queue.append(next)
            dist += 1
        return res

golang 解法, 执行用时: 156 ms, 内存消耗: 40.9 MB, 提交时间: 2023-10-21 19:39:33

func distanceToCycle(n int, edges [][]int) []int {
	g := make([][]int, n)
	deg := make([]int, n)
	for _, e := range edges {
		v, w := e[0], e[1]
		g[v] = append(g[v], w)
		g[w] = append(g[w], v) // 建图
		deg[v]++
		deg[w]++
	}

	// 拓扑排序，剪掉所有树枝
	q := []int{}
	for i, d := range deg {
		if d == 1 {
			q = append(q, i)
		}
	}
	for len(q) > 0 {
		v := q[0]
		q = q[1:]
		for _, w := range g[v] {
			if deg[w]--; deg[w] == 1 {
				q = append(q, w)
			}
		}
	}

	// 从基环出发，求所有树枝上的点的深度
	ans := make([]int, n)
	var f func(int, int)
	f = func(v, fa int) {
		for _, w := range g[v] {
			if w != fa && deg[w] < 2 {
				ans[w] = ans[v] + 1
				f(w, v)
			}
		}
	}
	for root, d := range deg {
		if d > 1 {
			f(root, -1)
		}
	}
	return ans
}