代碼隨想錄圖論并查集 第七天 | 685.冗余連接II

一、685.冗余連接II

題目鏈接：https://leetcode.cn/problems/redundant-connection-ii/
思路：684.冗余連接中是連通且無環(huán)的無向圖可直接使用并查集模板，如果想判斷集合中是否有環(huán)，且那條邊構(gòu)成環(huán)，只需要每次加入并查集之前先判斷一下是否有相同的根，有即構(gòu)成環(huán)。
本題是有向圖，如果不是樹，有兩種情況一種是入度為2，如[1,2]、[1,3]、[2,3]。3的入度為2刪掉一條邊即為樹。另一種是無入度為2的點，本身來說，本題原集合不是樹，如果無入度為2那么就一定構(gòu)成環(huán)了，如[1,2]、[2,3]、[3,1]。
那么，分為兩步，第一步找到入度為2的點，進行刪除嘗試，如果沒有入度為2的點，開始第二步，找到構(gòu)成環(huán)的邊。文章來源地址http://www.zghlxwxcb.cn/news/detail-740783.html

class Solution {
    int[] father = new int[1005];;


    public int[] findRedundantDirectedConnection(int[][] edges) {
        int[] inDegree = new int[1005];
        for (int i = 0; i < edges.length; i++) {
            inDegree[edges[i][1]]++;
        }
        List<Integer> list = new ArrayList<>();
        for (int i = edges.length -1; i >= 0 ; i--) {
            if (inDegree[edges[i][1]] == 2) list.add(i);
        }
        if (!list.isEmpty()) {
            if (f1(edges, list.get(0))) return edges[list.get(0)];
            else return edges[list.get(1)];
        }
        return f2(edges);
    }

    boolean f1(int[][] edges, int x) {
        init();
        for (int i = 0; i < edges.length; i++) {
            if (i == x) continue;
            if (isSame(edges[i][0], edges[i][1])) return false;
            else join(edges[i][0], edges[i][1]);
        }
        return true;
    }

    int[] f2(int[][] edges) {
        init();
        for (int[] edge : edges) {
            if (isSame(edge[0], edge[1])) return edge;
            else join(edge[0], edge[1]);
        }
        return null;
    }

    void init() {
        for (int i = 0; i < father.length; i++) {
            father[i] = i;
        }
    }
    int find(int u) {
        if (father[u] == u) return u;
        return father[u] = find(father[u]);
    }
    void join(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v)return;
        father[u] = v;
    }
    boolean isSame(int u, int v) {
        u = find(u);
        v = find(v);
        return u == v;
    }
}

到了這里，關(guān)于代碼隨想錄圖論并查集 第七天 | 685.冗余連接II的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！