🥹含泪总结周赛中的两道「图」问题

6134. 找到离给定两个节点最近的节点

6135. 图中的最长环

本周周赛后两题都是和「图」有关的，其中一个是「最短路径」问题，另一个是「环」问题

找到离给定两个节点最近的节点

题目详情可见 找到离给定两个节点最近的节点

首先看到这个题目，可以想到求出node1和node2到其它所有点的最短距离，然后遍历可选择的「中间点」。所以现在的问题就是如何求出其它点到起点的最短路径

「最短路径」算法有 最短路径-Dijkstra 和 无权值最短路径算法（BFS）

• 「Dijkstra」适用于加权有向图，没有负权重边，且无环，一般是求起点到其它所有点的最短路径，也可以改进为求两点的最短路径
• 「无权值最短路径算法（BFS）」适用于无权有向图，可以有环，一般是求两点的最短路径，也可以改进为求起点到其它所有点的最短路径

对于本题，每条边的权重均为 1，所以可以看作为无权值，我们使用上述的第二种方法「无权值最短路径算法（BFS）」

由于点与点之间最多只有一条边，所以可以简化「无权值最短路径算法（BFS）」

下面给出详细代码：

public int closestMeetingNode(int[] edges, int node1, int node2) {
    int n = edges.length;
    // 点 node1 和 node2 到其它所有点的最短路径
    int[] dist1 = getDist(edges, node1);
    int[] dist2 = getDist(edges, node2);
    int ans = -1, min = (int) 1e5 + 7;
    // 遍历可选择的「中间点」
    for (int i = 0; i < n; i++) {
        // 分别为 node1 和 node2 到 i 的最短路径
        int d1 = dist1[i], d2 = dist2[i];
        // 如果有一方到不了，则跳过
        if (d1 == -1 || d2 == -1) continue;
        int max = Math.max(d1, d2);
        if (max < min) {
            min = max;
            ans = i;
        }
    }
    return ans;
}
// 求点 s 到其它所有点的最短路径
private int[] getDist(int[] edges, int s) {
    int d = 0;
    int[] dist = new int[edges.length];
    Arrays.fill(dist, -1);
    while (s != -1) {
        // 已经访问，考虑「环」的存在
        if (dist[s] != -1) break;
        dist[s] = d++;
        // 下一个点
        s = edges[s];
    }
    return dist;
}

图中的最长环

题目详情可见 图中的最长环

关于「拓扑排序」的详细介绍可见 环检测 & 拓扑排序

先利用「拓扑排序」，找出所有不在环中的节点，那么剩余的节点全在环中

如图，会把点1和2删去，留下两个环中的点

下面给出详细代码：

public int longestCycle(int[] edges) {
    int n = edges.length;
    // 计算每个节点的入度
    int[] indegree = new int[n];
    for (int i = 0; i < n; i++) {
        if (edges[i] == -1) continue;
        indegree[edges[i]]++;
    }
    boolean[] notInCycle = new boolean[n];
    Queue<Integer> q = new LinkedList<>();
    // 入度为 0 的节点加入队列
    for (int i = 0; i < n; i++) {
        if (indegree[i] == 0) q.offer(i);
    }
    // 找出所有不在环中的节点
    while (!q.isEmpty()) {
        int cur = q.poll();
        // 标记点是否在环中
        notInCycle[cur] = true;
        if (edges[cur] == -1) continue;
        if (--indegree[edges[cur]] == 0) q.offer(edges[cur]);
    }
    int ans = -1;
    for (int i = 0; i < n; i++) {
        // 不在环中，跳过
        if (notInCycle[i]) continue;
        indegree[i] = 0;
        int cnt = 0;
        q.offer(i);
        // 求一个环的长度
        while(!q.isEmpty()) {
            int cur = q.poll();
            cnt++;
            notInCycle[i] = true;
            if (--indegree[edges[cur]] == 0) q.offer(edges[cur]);
        }
        // 更新 ans
        ans = Math.max(ans, cnt);
    }
    return ans;
}