代码随想录算法训练营第五十八天|108.冗余连接、109.冗余连接II

108.冗余连接

题目链接：108.冗余连接
文档讲解：代码随想录
状态：还行

思路：
并查集可以解决什么问题：两个节点是否在一个集合，也可以将两个节点添加到一个集合中。

题解：

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // 读取图中的边数
        UnionFind uf = new UnionFind(n + 1); // 初始化并查集，节点数为n+1
        for (int i = 0; i < n; i++) {
            int s = scanner.nextInt(); // 读取一条边的起点
            int t = scanner.nextInt(); // 读取一条边的终点
            if (uf.isSame(s, t)) { // 判断起点和终点是否属于同一个集合
                System.out.println(s + " " + t); // 如果是同一个集合，输出这条冗余边
                return; // 结束程序
            }
            uf.join(s, t); // 将起点和终点加入同一个集合
        }
    }

    static class UnionFind {
        private int n; // 节点数
        private int[] father; // 父节点数组

        public UnionFind(int n) {
            this.n = n; // 初始化节点数
            father = new int[n]; // 初始化父节点数组
            init(); // 初始化父节点数组
        }

        private void init() {
            for (int i = 0; i < n; i++) {
                father[i] = i; // 将每个节点的父节点初始化为自身
            }
        }

        private int find(int u) {
            // 查找节点u的根节点，并进行路径压缩
            return father[u] == u ? u : (father[u] = find(father[u]));
        }

        public void join(int u, int v) {
            // 将节点u和节点v的集合合并
            u = find(u); // 找到节点u的根节点
            v = find(v); // 找到节点v的根节点
            if (u != v) {
                father[v] = u; // 将节点v的根节点设置为u
            }
        }

        public boolean isSame(int u, int v) {
            // 判断节点u和节点v是否属于同一个集合
            return find(u) == find(v);
        }
    }
}

109.冗余连接II

题目链接：109.冗余连接II
文档讲解：代码随想录
状态：不会

思路：

可能情况
1.存在有环边

2.存在入度为2的顶点

3.同时存在有环边和入度为2的顶点

解题思路可以分为三种情况：

节点的入度为2：如果一个节点有两条入边，删除其中一条边会使得图变成树。
构成环的边：如果没有节点的入度为2，那么一定有一个环。删除环中的任意一条边会使得图变成树。

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // 读取图中的节点数
        int[][] edges = new int[n][2]; // 存储每条边的起点和终点
        int[] inDegree = new int[n + 1]; // 记录每个节点的入度
        UnionFind uf = new UnionFind(n + 1); // 初始化并查集，节点数为n+1
        for (int i = 0; i < n; i++) {
            int s = scanner.nextInt(); // 读取一条边的起点
            int t = scanner.nextInt(); // 读取一条边的终点
            inDegree[t]++; // 终点节点的入度加1
            edges[i][0] = s;
            edges[i][1] = t;
        }
        List<Integer> vec = new ArrayList<>(); // 记录入度为2的边（如果有的话就两条边）
        // 找入度为2的节点所对应的边，注意要倒序，因为优先删除最后出现的一条边
        for (int i = n - 1; i >= 0; i--) {
            if (inDegree[edges[i][1]] == 2) {
                vec.add(i);
            }
        }
        if (!vec.isEmpty()) {
            // 放在vec里的边已经按照倒叙放的，所以这里就优先删vec.get(0)这条边
            if (uf.isTreeAfterRemoveEdge(edges, vec.get(0), n)) {
                System.out.println(edges[vec.get(0)][0] + " " + edges[vec.get(0)][1]);
            } else {
                System.out.println(edges[vec.get(1)][0] + " " + edges[vec.get(1)][1]);
            }
            return;
        }
        // 处理情况三
        // 明确没有入度为2的情况，那么一定有有向环，找到构成环的边返回就可以了
        uf.getRemoveEdge(edges, n);
    }

    // 并查集类
    static class UnionFind {
        private int n; // 节点数
        private int[] father; // 父节点数组

        public UnionFind(int n) {
            this.n = n; // 初始化节点数
            father = new int[n]; // 初始化父节点数组
            init(); // 初始化父节点数组
        }

        private void init() {
            // 将每个节点的父节点初始化为自身
            for (int i = 0; i < n; i++) {
                father[i] = i;
            }
        }

        // 查找节点u的根节点，并进行路径压缩
        private int find(int u) {
            if (u != father[u]) {
                father[u] = find(father[u]);
            }
            return father[u];
        }

        // 将节点u和节点v的集合合并
        public void join(int u, int v) {
            u = find(u); // 找到节点u的根节点
            v = find(v); // 找到节点v的根节点
            if (u != v) {
                father[v] = u; // 将节点v的根节点设置为u
            }
        }

        // 判断节点u和节点v是否属于同一个集合
        public boolean isSame(int u, int v) {
            return find(u) == find(v);
        }

        // 在有向图里找到删除的那条边，使其变成树
        void getRemoveEdge(int[][] edges, int n) {
            init(); // 初始化并查集
            for (int i = 0; i < n; i++) { // 遍历所有的边
                if (isSame(edges[i][0], edges[i][1])) { // 构成有向环了，就是要删除的边
                    System.out.println(edges[i][0] + " " + edges[i][1]);
                    return;
                } else {
                    join(edges[i][0], edges[i][1]);
                }
            }
        }

        // 删一条边之后判断是不是树
        boolean isTreeAfterRemoveEdge(int[][] edges, int deleteEdge, int n) {
            init(); // 初始化并查集
            for (int i = 0; i < n; i++) {
                if (i == deleteEdge) continue; // 跳过要删除的边
                if (isSame(edges[i][0], edges[i][1])) { // 构成有向环了，一定不是树
                    return false;
                }
                join(edges[i][0], edges[i][1]);
            }
            return true;
        }
    }
}