基环树、拓扑排序和时间戳总结

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

这题是求点到点之间距离的问题，要点是一直循环记录就可以，退出条件为检测到成环了或者走到尽头

由于每个节点 至多 有一条出边，因此变成了一条没有分叉的路，BFS或者DFS都是可以的

public int closestMeetingNode(int[] edges, int node1, int node2) {
    /*
    基环树问题：
    直接预处理出node1以及node2到其他所有点的距离
    然后枚举每个节点，求出两者最大距离的最小时对应的节点索引返回
    时间复杂度:O(N) 空间复杂度:O(N)
     */
    int n = edges.length;
    // dis1[i]存储node1到节点编号为i的节点距离，dis2[i]存储node2到节点编号为i的节点距离(不能到达为-1)
    int[] dis1 = new int[n], dis2 = new int[n];
    Arrays.fill(dis1, -1);
    dis1[node1] = 0;
    Arrays.fill(dis2, -1);
    dis2[node2] = 0;
    getDis(edges, node1, dis1);
    getDis(edges, node2, dis2);
    int res = -1;   // 结果
    int min = 100010;
    for (int i = 0; i < n; i++) {
        if (dis1[i] == -1 || dis2[i] == -1) continue;   // 只有两个都可以到达才进行统计
        int curMax = Math.max(dis1[i], dis2[i]);
        if (curMax < min){
            min = curMax;
            res = i;
        }
    }
    return res;
}

// 获取node到节点i的距离并写入dis[i]
private void getDis(int[] edges, int node, int[] dis) {
    int cur = node, d = 0;
    // 当有可以前往的节点，继续走
    while (edges[cur] != -1) {
        cur = edges[cur];   // 走到下一个节点
        d++;
        if (dis[cur] != -1) break; // 成环访问到同一个节点了，退出
        dis[cur] = d;
    }
}

基环树定义可参考：【算法笔记】基环树

LC6135. 图中的最长环

这题也是基环树，因为出边限定了一条，但是可能有多个环

DFS时间戳一般是 times[i] 的形式，times[i] 记录的是首次访问节点 i 的时间节点

通过时间戳我们可以很轻易地得知该轮之前已经访问过了哪些节点并计算出距离

同时得知之前轮已经访问过的点，是一个兼具标记访问、标记先后顺序、标记距离、前缀和等参数的利器

可以用来判断是否成环、判断节点的父子关系等

class Solution {
    public int longestCycle(int[] edges) {
        /*
        基环树+时间戳
        times[i]记录首次访问编号为i的节点时间点，clock维护当前的时间节点
        我们枚举每个出发点
        1.遇到之前访问过的节点times[i]>0，跳过
        2.首次访问节点i，从节点i出发向前走同时标记访问过的节点的时间戳
        如果前方出现过times[j]>0的情况说明这个时候节点已经被访问过，说明成环了
        注意:为了避免后面枚举的节点重复经过之前访问过的节点但是不成环的情况，要加一个判断条件times[j]>=start
        其中start为从i点出发的时间戳，若成环必然有times[j]>=start，重复经过旧节点但是不成环的情况是times[j]<start
        因为你这个times[j]之前一轮出发点中已经枚举过了，时间必定在该轮start之前
        维护这个环的长度最大值就是答案
        时间复杂度:O(N) 空间复杂度:O(N)
         */
        int res = -1;
        int n = edges.length;
        int[] times = new int[n];
        // 枚举每个出发点
        for (int i = 0, clock = 1; i < n; i++) {
            if (times[i] > 0) continue; // 这个出发点已经访问过了，跳过
            int start = clock;  // start维护当前出发点的出发时间
            // 枚举以节点i为出发点的路径上的点
            for (int x = i; x != -1; x = edges[x]) {
                if (times[x] > 0) { // 已经访问过该节点(不一定是该轮的)
                    // 若该节点是该轮才访问的说明成环了
                    if(times[x] >= start) res = Math.max(res, clock - times[x]);  // 维护最大环值
                    break;  // 已经访问过节点就退出，不论是该轮访问的还是之前
                }
                times[x] = clock++; // 标记访问该节点的最早时间戳
            }
        }
        return res;
    }
}

LC2322. 从树中删除边的最小分数

class Solution {
    int[] nums, xr, in, out; // xr[i]为以i为根的子树异或和,in和out分别是节点i dfs递归进栈和出栈的时间点
    int clock = 0;  // 全局时间戳(以0为根的dfs序)
    List<Integer>[] list;   // 存边

    public int minimumScore(int[] _nums, int[][] edges) {
        /*
        DFS时间戳+枚举新树根节点+异或性质运用:
        题目是将整棵树切成3部分,我们就假设0为树原来的根节点(确定根节点方便求异或),切割之后另外两棵子树根节点为x与y
        假设x是y的根节点,由于枚举的是不同的点,因此不存在互相包含的情况
        此时有:in[x]<in[y]<=out[y]<=out[x] 其中in[y]<=out[y]必定成立,因此x是y的根节点等价于in[x]<in[y]&&out[y]<=out[x]
        利用时间戳的可以用来快速判断x与y节点之间的父子关系(以0为原始根节点)
        我们枚举删除边后产生的两个新的根节点,设a,b,c分别为0,x,y为根的切断后子树异或和,有以下3种情况:
        1.x是y的根节点且位于初始根节点0的同侧->异或和分别为:c=xr[y],b=xr[x]^xr[y],a=xr[0]^xr[x]
        2.y是x的根节点且位于初始根节点0的同侧->异或和分别为:b=xr[x],c=xr[y]^xr[x],a=xr[0]^xr[y]
        3.y与x分局初始根节点0的异侧->异或和分别为:c=xr[y],b=xr[x],a=xr[0]^xr[x]^xr[y]
        分别枚举x∈[1,n],y∈[x+1,n],维护异或和差值的最小值
         */
        nums = _nums;
        int res = 0x3f3f3f3f, n = nums.length;
        xr = new int[n];
        in = new int[n];
        out = new int[n];
        list = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            list[i] = new ArrayList<>();
        }
        for (int[] e : edges) {
            int a = e[0], b = e[1];
            list[a].add(b);
            list[b].add(a);
        }
        dfs(0, -1); // 初始化各个节点时间戳以及求每个节点为根的异或和
        // 枚举删除边后产生的两个新的根节点x与y
        int a, b, c;    // 设a,b,c分别为0,x,y为根切断后子树的异或和
        for (int x = 1; x < n; x++) {
            for (int y = x + 1; y < n; y++) {
                if (isParent(x, y)) {   // x是y根节点
                    a = xr[0] ^ xr[x];
                    b = xr[x] ^ xr[y];
                    c = xr[y];
                } else if (isParent(y, x)) {    // y是x根节点
                    a = xr[0] ^ xr[y];
                    b = xr[x];
                    c = xr[y] ^ xr[x];
                } else {    // x与y分布异侧
                    a = xr[0] ^ xr[x] ^ xr[y];
                    b = xr[x];
                    c = xr[y];
                }
                // 维护异或和最大差值的最小值
                int max = Math.max(a, Math.max(b, c)), min = Math.min(a, Math.min(b, c));
                res = Math.min(res, max - min);
                if (res == 0) return 0; // 为0提前退出
            }
        }
        return res;
    }

    // 判断x是否为y的父节点(不重合)
    private boolean isParent(int x, int y) {
        return in[x] < in[y] && out[y] <= out[x];
    }

    // 求节点时间戳和异或和:其中i为当前节点索引,fa为其父节点(用于避免走回头路)
    private void dfs(int i, int fa) {
        xr[i] = nums[i];    // xr[i]初始化为节点i的值
        in[i] = ++clock;    // 记录进入的时间戳
        for (int next : list[i]) {
            if (next != fa) {   // 不走回头路
                dfs(next, i);   // 求出以next为根的异或和与时间戳
                xr[i] ^= xr[next];  // xr[i]添上xr[next]
            }
        }
        out[i] = clock; // 记录i出栈时间戳
    }
}

拓扑排序检测环的应用：

拓扑排序可以将不在环中的节点先全部删除掉然后就会剩下只在环中的节点

可以统计删除的节点数目对比总节点的数目就可以得知是否存在环

环中的节点个数可以直接通过for循环遍历进行统计

public int longestCycle(int[] edges) {
    /*
    基环树+拓扑排序
    拓扑排序可以优先逐步筛选掉那些入度为0的节点，最后就只剩下成环的节点了
    拓扑排序总体思路为:
    1.定义入度数组并统计每个节点的入度，首次先将入度为0点节点入队
    2.将上一轮的入队的节点的弹出删除，并将出队节点指向的节点入度-1，如果此时又有节点入度为0就入队，以此类推直至队列为空
    (注意上述过程入队的节点都要进行标记后面不能再用)
    3.剩下的节点就是成环的，入度永远也不可能为0的节点了
        这里可以提前判断一下剩余节点个数是不是为0了，如果是可以提前退出
    4.枚举每个节点进行for循环遍历(因为只有一条出边因此可以用for循环代替DFS/BFS)
        如果已经删除掉的就跳过，如果不是就证明这个节点必然在环中，直接for循环遍历并统计最大长度
        遍历过的环同样进行标记避免下一次重复访问
        那么最后统计到的最大长度就是最长环
    时间复杂度:O(N) 空间复杂度:O(N)
     */
    int n = edges.length;
    boolean[] vis = new boolean[n];
    Queue<Integer> que = new LinkedList<>();    // 辅助队列
    int[] inDegree = new int[n];    // 入度数组
    for (int e : edges) {
        if (e != -1) inDegree[e]++;
    }
    // 入度为0的节点优先入队
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) {
            que.add(i);
            vis[i] = true;  // 标记访问
        }
    }
    while (!que.isEmpty()) {
        int poll = que.poll();  // 删除节点poll
        int next = edges[poll]; // 指向的节点索引
        // 注意可能不成环的情况next在最后一个节点为-1，因此要加一个判断
        if (next != -1 && --inDegree[next] == 0) { // 由于删除了节点poll因此其指向的节点对应入度也-1，若为0就入队
            que.add(next);
            vis[next] = true;
        }
    }
    int res = -1;
    // 剩下的节点就是环上的节点
    for (int i = 0; i < n; i++) {
        if (vis[i]) continue;   // 访问过的节点跳过
        // 否则就是未访问过的环上的节点
        int cur = i, cycleNum = 0;
        while (!vis[edges[cur]]) {
            cur = edges[cur];
            cycleNum++;
            vis[cur] = true;
        }
        res = Math.max(res, cycleNum);  // 维护环的最大值
    }
    return res;
}

LC6163. 给定条件下构造矩阵

拓扑排序的题目通常是：已知一系列限制某两个节点先后顺序的条件，要求解最后满足这些条件的节点总体先后顺序。

这道题就是典型的拓扑排序问题，条件可以看做边，只要得知两个维度可以独立分析，那么这道题就可以拆解成两次拓扑排序。

class Solution {
    public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {
        /*
        维度独立分析+拓扑排序:
        注意到:两个维度之间的顺序是独立的，只要各自满足该维度的排序最后进行组装即可
        而且数字之间的先后可以看做有向边，求节点的先后顺序就是典型的拓扑排序问题
         */
        // 求出两个维度限制条件计算出来的顺序
        List<Integer> seq1 = getSeq(k, rowConditions), seq2 = getSeq(k, colConditions);
        // 成环了，seq的长度必然小于k，没有答案
        if (seq1.size() < k || seq2.size() < k) return new int[0][0];
        // 根据seq1与seq2组装成矩阵
        int[][] res = new int[k][k];
        int[][] map = new int[k + 1][2];    // 索引映射
        for (int i = 0; i < k; i++) {
            map[seq1.get(i)][0] = i;
            map[seq2.get(i)][1] = i;
        }
        for (int i = 1; i <= k; i++) {
            res[map[i][0]][map[i][1]] = i;
        }
        return res;
    }

    // 根据限制条件，通过拓扑排序获取节点的相对顺序(返回某一种合法情况)
    private List<Integer> getSeq(int k, int[][] conditions) {
        int[] inDegree = new int[k + 1];
        HashSet<Integer>[] list = new HashSet[k + 1];
        for (int i = 1; i <= k; i++) {
            list[i] = new HashSet<>();
        }
        for (int[] r : conditions) {
            // a->b 即a在b上面
            int a = r[0], b = r[1];
            // HashSet自动去判断是否存在并添加(去重)
            if (list[a].add(b)) {
                inDegree[b]++;
            }
        }
        List<Integer> seq = new ArrayList<>();  // 存储顺序
        Queue<Integer> que = new LinkedList<>();
        // 入度为0的先入队
        for (int i = 1; i <= k; i++) {
            if (inDegree[i] == 0) {
                que.add(i);
                seq.add(i);    // 加入seq
            }
        }
        while (!que.isEmpty()) {
            int poll = que.poll();  // 删除该边
            for (int ne : list[poll]) {
                // 删除poll后如果产生入度为0的节点就使其入队
                if (--inDegree[ne] == 0) {
                    que.add(ne);
                    seq.add(ne);    // 加入seq
                }
            }
        }
        return seq;
    }
}