Day58:并查集 108.冗余连接 109.冗余连接II

108. 冗余连接

时间限制：1.000S  空间限制：256MB

题目描述

树可以看成是一个图（拥有 n 个节点和 n - 1 条边的连通无环无向图）。 

现给定一个拥有 n 个节点（节点标号是从 1 到 n）和 n 条边的连通无向图，请找出一条可以删除的边，删除后图可以变成一棵树。

输入描述

第一行包含一个整数 N，表示图的节点个数和边的个数。

后续 N 行，每行包含两个整数 s 和 t，表示图中 s 和 t 之间有一条边。

输出描述

输出一条可以删除的边。如果有多个答案，请删除标准输入中最后出现的那条边。

输入示例

3
1 2
2 3
1 3

输出示例

1 3

提示信息

图中的 1 2，2 3，1 3 等三条边在删除后都能使原图变为一棵合法的树。但是 1 3 由于是标准输出里最后出现的那条边，所以输出结果为 1 3

数据范围：

1 <= N <= 1000.

思路:

这道题目也是并查集基础题目。

从前向后遍历每一条边（因为优先让前面的边连上),边的两个节点如果不在同一个集合，就加入集合（即：同一个根节点）。

节点A 和节点 B 不在同一个集合，那么就可以将两个节点连在一起。

如果边的两个节点已经出现在同一个集合里，说明着边的两个节点已经连在一起了，再加入这条边一定就出现环了。

已经判断 节点1和 节点3 在在同一个集合（同一个根），如果将 节点1 和 节点3连在一起就一定会出现环。 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int n;
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        M m = new M(n);
        while (in.hasNextLine()) {
            int x = in.nextInt();
            int y = in.nextInt();
            if (m.isSame(x, y)) {
                System.out.println(x + " " + y);
                return;
            }
            m.join(x, y);
        }


    }

}

class M {
    int[] father;

    public M(int n) {
        father = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            father[i] = i;
        }
    }

    int find(int i) {
        if (father[i] == i) {
            return i;
        }
        father[i] = find(father[i]);
        return father[i];
    }

    boolean isSame(int i, int j) {
        i = find(i);
        j = find(j);
        if (i == j) return true;
        return false;
    }

    void join(int i, int j) {
        i = find(i);
        j = find(j);
        if (i == j) return;
        father[j] = i;
    }
}

109. 冗余连接II

时间限制：1.000S  空间限制：256MB

题目描述

有向树指满足以下条件的有向图。该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。有根树拥有 n 个节点和 n - 1 条边。 

输入一个有向图，该图由一个有着 n 个节点(节点编号 从 1 到 n)，n 条边，请返回一条可以删除的边，使得删除该条边之后该有向图可以被当作一颗有向树。

输入描述

第一行输入一个整数 N，表示有向图中节点和边的个数。 

后续 N 行，每行输入两个整数 s 和 t，代表 s 节点有一条连接 t 节点的单向边

输出描述

输出一条可以删除的边，若有多条边可以删除，请输出标准输入中最后出现的一条边。

输入示例

3
1 2
1 3
2 3

输出示例

2 3

提示信息

在删除 2 3 后有向图可以变为一棵合法的有向树，所以输出 2 3

数据范围：

1 <= N <= 1000.

思路:

本题的本质是 ：有一个有向图，是由一颗有向树 + 一条有向边组成的 （所以此时这个图就不能称之为有向树），现在让我们找到那条边 把这条边删了，让这个图恢复为有向树。

还有“若有多条边可以删除，请输出标准输入中最后出现的一条边”，这说明在两条边都可以删除的情况下，要删顺序靠后的边！

向树的性质，如果是有向树的话，只有根节点入度为0，其他节点入度都为1（因为该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点）。

如果发现入度为2的节点，我们需要判断 删除哪一条边(导致入度为2的边)，删除后本图能成为有向树。如果是删哪个都可以，优先删顺序靠后的边。

删除特定的边才能变成有向树 

删除多条都可以,则删除最后加入的那条 

如果没有入度为2的点，说明 图中有环了（注意是有向环）。对于情况二，删掉构成环的边就可以了。

isTreeAfterRemoveEdge()判断删一个边之后是不是有向树(没有环且没有)： 将所有边的两端节点分别加入并查集，遇到要 要删除的边则跳过，如果遇到即将加入并查集的边的两端节点 本来就在并查集了，说明构成了环。

如果顺利将所有边的两端节点（除了要删除的边）加入了并查集，则说明 删除该条边 还是一个有向树

 getRemoveEdge()确定图中一定有了有向环，那么要找到需要删除的那条边： 将所有边的两端节点分别加入并查集，如果遇到即将加入并查集的边的两端节点 本来就在并查集了，说明构成了环。

代码参考:

import java.util.*;

public class Main {
    private static M m;

    public static void main(String[] args) {
        int n;
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = new M(n);
        int[] inDegree = new int[n + 1];
        List<List<Integer>> edges = new LinkedList<>();
        while (n-->0) {
            int x = in.nextInt();
            int y = in.nextInt();
            //记录下每个点的入度

            inDegree[y]++;
            List<Integer> list = Arrays.asList(x, y);
            edges.add(list);
        }

        List<Integer> inedges2 = new LinkedList<>();
        //找到入度为2的边
        for (int i = edges.size() - 1; i >= 0; i--) {
            if (inDegree[edges.get(i).get(1)] == 2) {
                inedges2.add(i);
            }
        }
      
        if (inedges2.size() >0) {
            if (isTreeAfterRemoveEdge(inedges2.get(0), edges)) {
                System.out.println(edges.get(inedges2.get(0)).get(0) + " " + edges.get(inedges2.get(0)).get(1));
            } else {
                System.out.println(edges.get(inedges2.get(1)).get(0) + " " + edges.get(inedges2.get(1)).get(1));
            }
        } else {
            getRemoveEdge(edges);
        }
    }

    public static void getRemoveEdge(List<List<Integer>> edges) {
        m.init();
        //遍历所有边,加入并查集
        for (List<Integer> list : edges) {
            if (m.isSame(list.get(0), list.get(1))) {
                System.out.println(list.get(0) + " " + list.get(1));
                return;
            } else {
                m.join(list.get(0), list.get(1));
            }
        }
    }

    //判断删除该边后是否为有向树
    public static boolean isTreeAfterRemoveEdge(int index, List<List<Integer>> edges) {
        m.init();
        for(int i=0;i<edges.size();i++){
            if(i!=index){
                if (m.isSame(edges.get(i).get(0),edges.get(i).get(1))){
                    return  false;
                }
                m.join(edges.get(i).get(0),edges.get(i).get(1));
            }
        }
       
        return true;
    }

}

class M {
    int[] father;

    public M(int n) {
        father = new int[n + 1];

    }

    void init() {
        for (int i = 1; i < father.length; i++) {
            father[i] = i;
        }
    }

    int find(int i) {
        if (father[i] == i) {
            return i;
        }
        father[i] = find(father[i]);
        return father[i];
    }

    boolean isSame(int i, int j) {
        i = find(i);
        j = find(j);
        if (i == j) return true;
        return false;
    }

    void join(int i, int j) {
        i = find(i);
        j = find(j);
        if (i == j) return;
        father[j] = i;
    }
}