并查集

发表于 | 分类于 | |
字数统计: 1,188 | 阅读时长 ≈ 6

引言

并查集是解决图的连通性的一种很简单的算法，能很清晰简单的解决图的连通性问题。

并查集的思想就是通过不停的Union操作，为每个节点找到它的最初父亲节点，就这样一步步的归并，就能把每个点聚集到自己的root节点上，这样就能快速的计算出图中各个节点的连通性了。

并查集的模板

  • 首先我们一般要先构造一下数据，每个节点的父亲设置为自己

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    typedef struct Node {
        int index;
        int father;
    } Node;

    vector<struct Node> nodeList;
    Node node;
    for (int i = 0; i < isConnected.size(); i++) {
        node.index = i;
        node.father = i;
        nodeList.emplace_back(node);
    }

  • 并查集中最重要的两个函数分别为Union和Find

    • Union用来将两个节点连接起来，也就是说如果我们两个节点是联通的，那么我的父亲节点将会变为你的父亲节点。

      1
      2
      3
      4
      5
      void Union(vector<Node>& nodeList, int i, int j) {
          int fatherI = Find(nodeList, i);
          int fatherJ = Find(nodeList, j);
          nodeList[fatherJ].father = fatherI;
      }

    • Find用来查找每个节点的父亲节点，这里一步一步的递归调用知道找到root节点。

      1
      2
      3
      4
      5
      6
      int Find(vector<Node>& nodeList, int index) {
          if (nodeList[index].father == index) {
              return index;
          }
          return Find(nodeList, nodeList[index].father);
      }

  • 最后通过检查集合中有几个节点的父节点依旧为自己，就能确定到底有多少的连通集合了。

    1
    2
    3
    4
    5
    6
    int count = 0;
    for (int i = 0; i < isConnected.size(); i++) {
        if (nodeList[i].father == i) {
            count++;
        }
    }

例子说明

547. 省份数量

这个题目很简单，直接套用上面的模板解决解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
typedef struct Node {
    int index;
    int father;
} Node;

class Solution {
public:
    int Find(vector<Node>& nodeList, int index) {
        if (nodeList[index].father == index) {
            return index;
        }
        return Find(nodeList, nodeList[index].father);
    }

    void Union(vector<Node>& nodeList, int i, int j) {
        int fatherI = Find(nodeList, i);
        int fatherJ = Find(nodeList, j);
        nodeList[fatherJ].father = fatherI;
    }

    int findCircleNum(vector<vector<int>>& isConnected) {
        vector<struct Node> nodeList;
        Node node;
        for (int i = 0; i < isConnected.size(); i++) {
            node.index = i;
            node.father = i;
            nodeList.emplace_back(node);
        }

        for(int i = 0;i < isConnected.size(); i++) {
            for (int j = 0; j < isConnected[0].size(); j++) {
                if (isConnected[i][j] == 1) {
                    Union(nodeList, i, j);
                }
            }
        }

        int count = 0;
        for (int i = 0; i < isConnected.size(); i++) {
            if (nodeList[i].father == i) {
                count++;
            }
        }
        return count;
    }
};

990. 等式方程的可满足性

同样的利用并查集来解决问题。依旧用的上面的三板斧。

如果等式相等，我们认为他们有相同的父节点。

在最后判断不等式的时候，需要再次查找其父节点，看其是否具有相同的父节点，如果有，则说明存在矛盾，因此应该返回false。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
typedef struct Node {
    int index;
    int father;
} Node;

class Solution {
public:
    int Find(vector<Node>& nodeList, int index) {
        if (nodeList[index].father == index) {
            return index;
        }
        return Find(nodeList, nodeList[index].father);
    }
    void Union(vector<Node>& nodeList, int i, int j) {
        int fatherI = Find(nodeList, i);
        int fatherJ = Find(nodeList, j);
        nodeList[fatherI].father = fatherJ;
    }
    bool equationsPossible(vector<string>& equations) {
        vector<Node> nodeList;
        Node node;
        for (int i = 0; i < 26; i++) {
            node.index = i;
            node.father = i;
            nodeList.emplace_back(node);
        }

        for (auto& item : equations) {
            if (item[1] == '=' && item[2] == '=') {
                Union(nodeList, item[0] - 'a', item[3] - 'a');
            }
        }

        for (auto& item : equations) {
            if (item[1] == '!' && item[2] == '=') {
                int father1 = Find(nodeList, item[0] - 'a');
                int father2 = Find(nodeList, item[3] - 'a');
                if (father1 == father2) {
                    return false;
                }
            }
        }
        return true;
    }
};

并查集的优化

上面的模板以及例题代码存在什么问题呢？我们在Union阶段是随机的把节点挂在另一个节点的父亲节点下，那么就会导致最终形成的树不均衡问题，极端情况下有可能树是一个链表，这样在find的时候就会导致耗时严重。

1
2
3
4
5
void Union(vector<Node>& nodeList, int i, int j) {
    int fatherI = Find(nodeList, i);
    int fatherJ = Find(nodeList, j);
    nodeList[fatherJ].father = fatherI;
}

那么怎样解决这个问题呢？一种方式是增加一个size变量

1
2
3
4
5
int[] size;
typedef struct Node {
    int index;
    int father;
} Node;

这样在Union的时候，首先比较size，层次浅的树挂到层次深的树上面

1
2
3
4
5
6
7
8
9
10
11
12
13
void Union(vector<Node>& nodeList, int i, int j) {
    int fatherI = Find(nodeList, i);
    int fatherJ = Find(nodeList, j);
    nodeList[fatherJ].father = fatherI;
    // 小树接到大树下面，较平衡
    if (size[fatherI] > size[fatherJ]) {
        nodeList[fatherJ].father = fatherI;
        size[fatherI] += size[fatherJ];
    } else {
        nodeList[fatherI].father = fatherJ;
        size[fatherI] += size[fatherJ];
    }
}

另一种方法是使用路径压缩，在每次find的时候，递归调用find方法，压缩父节点。

1
2
3
4
5
6
public int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

显示 Gitment 评论