1.并查集模板
并查集是一种树型数据结构(多叉树),可以高效地实现查找和合并功能,常用于求连通问题
1.每个数据可以看作一个节点
2.每一组数据都是一颗树
3.一个组中的数据对应的树和另外一个组中数据对应的树之间没有任何关系
4.初始化的时候把索引当作每个组的标识符
并查集主要有三个功能:
1.寻找根节点,函数:find(int u),也就是判断这个节点的祖先节点是哪个
2.将两个节点接入到同一个集合,函数:join(int u, int v),将两个节点连在同一个根节点上
3.判断两个节点是否在同一个集合,函数:same(int u, int v),就是判断两个节点是不是同一个根节点
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
| int n = 1005; int[] father = new int[n];
void init() { for (int i = 0; i < n; ++i) { father[i] = i; } }
int find(int u) { if(father[u]!=u) father[u]=find(father[u]); return father[u]; }
void join(int u, int v) { u = find(u); v = find(v); if (u == v) return; father[v] = u; }
boolean same(int u, int v) { u = find(u); v = find(v); return u == v; }
|
注意: 每个连通域根节点都是独一无二的,因此可以通过某个节点寻根+HashMap统计出每个连通域的节点数量以及连通域个数等,而不用多一个字段值sum,代码如下:
1 2 3 4 5 6 7 8 9 10
| for (int[] e : edges) { join(e[0], e[1]); }
HashMap<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < n; i++) { int root = find(i); map.put(root, map.getOrDefault(root, 0) + 1); }
|
map.size()
就是连通域数量;map.get(find(x))
就是节点x所在连通域节点数量