并查集理论基础

并查集用来解决连通性问题

连通图 + 强连通图

在无向图中，任何两个节点都是可以到达的，我们称之为连通图；如果有节点不能到达其他节点，则为非连通图。

在有向图中，任何两个节点都是可以到达的，我们称之为强连通图。与无向图中的连通图有些不同，因为强连通图是有向图作为基础的，必须任何两个节点都是可以相互到达的，所以要么两节点是双向连接的，要么整个图成环。

何为解决连通性问题？通俗理解就是判断两个元素是否在同一个集合里。

并查集主要有两个功能：

功能一：将两个(或多个)元素添加到一个集合中；

功能二：判断两个(或多个)元素在不在同一个集合。

先来看功能一如何实现：将两个(或多个)元素添加到一个集合中。

我们将三个元素A，B，C（分别是数字）放在同一个集合，其实就是将三个元素连通在一起，如何连通呢？

只需要用一个一维数组来表示，即：father[A] = B,（表示A指向B），father[B] = C，（表示B指向C），这样一来就表示A与B与C连通了（有向连通图）。

代码如下：

//将节点 v 指向 节点 u 的这条边 加入 并查集
void join(int u, int v){
   u = find(u);//找节点u的根节点，并赋值为u
   v = find(v);//找节点v的根节点，并赋值为v
   if(u == v) return;//如果节点u和节点v的根节点是同一个，则说明在同一个集合中，不用两个节点相连直接返回即可
   father[v] = u;//说明两个节点根节点不是一个，那么就把两个节点相连，节点v指向节点u
}

至此，通过join方法实现了功能一。我们可以知道A连通B，因为A是索引下标，根据father[A]的数值就可以知道A连通B。那么怎么知道B连通A呢？

因为我们的目的是实现功能二：判断多个元素是否在同一个集合中，所以知道A连通B就已经足够了。

寻根思路就是A，B，C在同一个根下就是同一个集合。

具体来说：给出A元素，就可以通过father[A] = B,father[B] = C,找到根为C

给出B元素，通过father[B] = C，找到根也为C。说明A和B是在同一个集合中。

代码如下：

//并查集寻根的过程
int find(int u){
    if(u == father[u]) return u;//如果根就是自己，直接返回
    else return find(father[u]); //如果根不是自己，就根据其父节点不断递归找到根节点
}

如何表示C也在同一个元素里呢？我们需要father[C] = C，即C的根也为C，这样就方便表示A，B，C都在同一个集合中了。

所以father数组初始化的时候要father[i] = i,默认自己指向自己

代码如下：

// 并查集初始化
void init(){
    for(int i = 0; i < n; i++){
      father[i] = i;
    }
}

最后再来看看如何实现功能二：判断两个(或多个)元素在不在同一个集合。

如果通过 find 函数 找到 两个元素属于同一个根的话，那么这两个元素就是同一个集合

代码如下：

// 判断 u 和 v 是否找到同一个根
boolean isSame(int u, int v){
    u = find(u);
    v = find(v);
    return u == v;
}

路径压缩：

在实现find函数的过程中，通过递归的方式，不断获取father数组下标对应的数值，最终找到这个集合的根。如果递归次数非常多会导致效率低。我们的目的只需要知道这些节点在同一个根下就可以，所以除了根节点其他所有节点都挂在根节点下，这样在寻根的时候就很快，只需要一步，由原来的时间复杂度O(logn)降为O(1)。

想要实现这样的效果，需要路径压缩，将非根节点的所有节点直接指向根节点。

只需要在递归的过程中，让 father[u] 接住 递归函数 find(father[u]) 的返回结果。

因为find 函数 向上寻找根节点，father[u]表述 u 的父节点，那么让 father[u] 直接获取 find 函数 返回的根节点，这样就让节点 u 的 父节点 变成 根节点。

代码如下：

//并查集寻根的过程
int find(int u){
    return u == father[u] ? u : father[u] = find(father[u]);  
}

综上：并查集主要有三个功能：

1.寻找根节点，函数：find(int u)，也就是判断节点u的根节点是哪个；

2.将两个节点接入到同一个集合，函数：join(int u, int v)，将两个节点连在同一个根节点下；

3.判断两个节点是否在同一个集合，函数：isSame(int u, int v)，就是判断两个节点是不是同一个根节点。

模板代码总结如下：

// 并查集初始化
void init(){
    for(int i = 0; i < n; i++){
      father[i] = i;
    }
}
//将节点 v 指向 节点 u 的这条边 加入 并查集
void join(int u, int v){
    u = find(u);//找节点u的根节点，并赋值为u
    v = find(v);//找节点v的根节点，并赋值为v
    if(u == v) return;//如果节点u和节点v的根节点是同一个，则说明在同一个集合中，不用两个节点相连直接返回即可
    father[v] = u;//说明两个节点根节点不是一个，那么就把两个节点相连，节点v指向节点u
}
//并查集寻根的过程
int find(int u){
    return u == father[u] ? u : father[u] = find(father[u]);  
}
// 判断 u 和 v 是否找到同一个根
boolean isSame(int u, int v){
    u = find(u);
    v = find(v);
    return u == v;
}

107.寻找存在的路径

通过并查集将图转成树的形式。判断两个节点在不在一个集合(就是判断两个节点是不是拥有同一个根节点)+将两个节点添加到一个集合中(就是将这两个节点都指向同一个根节点)。

代码如下：

import java.util.*;

//并查集
public class Main{
    public static void main (String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        DisJoint disJoint = new DisJoint(n);
        for(int i = 0; i < m; i++){
            int s = scanner.nextInt();
            int t = scanner.nextInt();
            disJoint.join(s, t);
        }
        int source = scanner.nextInt();
        int destination = scanner.nextInt();
        if(disJoint.isSame(source, destination) == true){
            System.out.print(1);
        }else{
            System.out.print(0);
        }
    }  
}
//并查集
class DisJoint{
    private int[] father;
    public DisJoint(int n){
        father = new int[n + 1];
        for(int i = 0; i <= n; i++){
            father[i] = i;
        }
    }
    public void join(int u, int v){
        u = find(u);
        v = find(v);
        if(u == v){
            return;
        }
        father[v] = u;
    }
    
    public int find(int u){
        return u == father[u] ? u : (father[u] = find(father[u]));
    }
    public boolean isSame(int u, int v){
        u = find(u);
        v = find(v);
        return u == v;
    }
}

108.冗余连接

解题思路：

从前向后遍历每一条边（优先让前面的边连上），边的两个节点如果不在同一个集合(isSame(u, v) == false)，那就加入集合(join(u, v))（即同一个根节点）。如果边的两个节点已经出现同一个集合中(isSame(u, v) == true)，说明这条边的两个节点已经连在一起了，再加入这条边就一定会成环。

代码如下：

import java.util.*;
//思路 ：如果两个节点 是 都指向同一个根节点(即是在同一个集合中)，那么再将这两个节点
//连起来，就一定构成环
public class Main{
    public static void main (String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        DisJoint disJoint = new DisJoint(n);
        for(int i = 0; i < n; i++){
            int s = scanner.nextInt();
            int t = scanner.nextInt();
            if(disJoint.isSame(s, t) == false){//说明两节点不在同一个集合
                //加入同一个集合
                disJoint.join(s, t);
            }else{//说明两节点在同一个集合
                System.out.print(s + " " + t);
            }
        }      
    }    
}

class DisJoint{
    private int[] father;
    public DisJoint(int n){
        father = new int[n + 1];
        for(int i = 0; i <= n; i++){
            father[i] = i;
        }
    }
    public void join(int u, int v){
        u = find(u);
        v = find(v);
        if(u == v){
            return;
        }
        father[v] = u;
    }
    public int find(int u){
        return u == father[u] ? u : (father[u] = find(father[u]));
    }
    public boolean isSame(int u, int v){
        u = find(u);
        v = find(v);
        return u == v;
    }  
}

109.冗余连接II

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

现在有一个有向图，有向图是在 有向树 中的两个没有直接连接 的 节点 中间添加一条有向边。所以有向图是有 n 个节点 和 n条边组成的。

现在需要返回一条可以删除的边，使得删除这条边之后 该有向图 变成了 一颗 有向树

解题思路：

有向树的性质是：只有根节点入度为0，其他节点入度都为1。

情况一：找到入度为2的点，那么删除一条指向该节点的边即可。

情况二：找到入度为2的点，但是只能删除特定的一条边。

情况三：如果没有入度为2的点，说明 图中 有环了，就和 冗余连接 那道题一样了，删除构成环的边即可。

具体写法步骤：

1、把每条边记录下来，并统计节点入度，这道题只会存在一个入度为2的点。

2、前两种入度为2的情况，一定是删除指向入度为2的节点的两条边其中的一条。如果删了一条，就判断这个图是不是一颗有向树，如果是，那么这条边就是答案；如果不是，就删除另外那条边。同时注意要从后向前遍历，因为如果两条边删哪一条都可以成为有向树，就删最后那一条。

3、第三种情况3，明确没有入度为2的情况下，那么一定有 有向环， 找到构成环 的 边就是要删除的边。

综上 我们 需要构建两个方法：

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

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

代码如下：

import java.util.*;

public class Main{
    static class Disjoint {

        private final int[] father;

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

        public void join(int n, int m) {
            n = find(n);
            m = find(m);
            if (n == m) return;
            father[n] = m;
        }

        public int find(int n) {
            return father[n] == n ? n : (father[n] = find(father[n]));
        }

        public boolean isSame(int n, int m) {
            return find(n) == find(m);
        }
    }
    
    static class Edge{
        int s;
        int t;
        public Edge(int s, int t){
            this.s = s;
            this.t = t;
        }
    }
    static class Node{
        int id;
        int in;
        int out;
    }
    public static void main (String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        //记录入度为2的节点是哪一个（本题只能有一个入度为2的点）
        //装填所有输入的节点以及对应的边信息
        List<Edge> edges = new ArrayList<>();
        Node[] nodeMap = new Node[n + 1];
        for (int i = 1; i <= n; i++) {
            nodeMap[i] = new Node();
        }
        int doubleIn = 0;
        for(int i = 0; i < n; i++){
            int s = scanner.nextInt();
            int t = scanner.nextInt();
            nodeMap[t].in++;
            if(nodeMap[t].in == 2){
                doubleIn = t;
            }
            edges.add(new Edge(s, t));
        }
        //开始走三个情况的逻辑
        Edge result = null;
        if(doubleIn != 0){//说明有入度为2的节点
            List<Edge> doubleInEdges = new ArrayList<>();
            for(Edge edge : edges){
                if(edge.t == doubleIn){
                    doubleInEdges.add(edge);
                }
                if(doubleInEdges.size() == 2){
                    break;
                }
            }
            Edge edge = doubleInEdges.get(1);
            if (isTreeAfterRemoveEdge(edges, edge, nodeMap)) {
                result = edge;
            } else {
                result = doubleInEdges.get(0);
            }
        }else{//说明没有入度为2的节点
            result = getRemoveEdge(edges, nodeMap);
        }
        System.out.println(result.s + " " + result.t);
    }
    public static boolean isTreeAfterRemoveEdge(List<Edge> edges, Edge exculdEdge, Node[] nodeMap) {
        Disjoint disjoint = new Disjoint(nodeMap.length - 1);
        for (Edge edge : edges) {
            if (edge == exculdEdge) continue;
            //成环则不是树
            if (disjoint.isSame(edge.s, edge.t)) {
                return false;
            }
            disjoint.join(edge.s, edge.t);
        }
        return true;
    }

    public static Edge getRemoveEdge(List<Edge> edges, Node[] nodeMap) {
        int length = nodeMap.length - 1;
        Disjoint disjoint = new Disjoint(length);

        for (Edge edge : edges) {
            if (disjoint.isSame(edge.s, edge.t)) return edge;
            disjoint.join(edge.s, edge.t);
        }
        return null;
    }  
}