关键词：
并查集--basic
public class UnionFind1 {
private int[] parent; //数组,表示并查集所有元素的集合号
private int size; //表示并查集元素个数
public UnionFind1(int size) { //并查集初始化
this.size = size;
parent = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i;
}
}
/**
* 查看元素所属集合
*
* @param element
* @return
*/
private int find(int element) {
return parent[element];
}
/**
* 判断两个集合是否在同一个集合
*
* @param firstElement
* @param secondElement
* @return
*/
public boolean isConnected(int firstElement, int secondElement) {
return find(firstElement) == find(secondElement);
}
/**
* 合并firstElement,secondElement两个元素所在集合
* 将firstElement集合中所有元素的集合号都变为secondElement,就是认为是将两个集合合并
*
* @param firstElement
* @param secondElement
*/
public void unionElements(int firstElement, int secondElement) {
int firstUnion = find(firstElement);
int secondUnion = find(secondElement);
if (firstUnion != secondUnion) {
for (int i = 0; i < size; i++) {
if (parent[i] == firstUnion) {
parent[i] = secondUnion;
}
}
}
}
private void printArray() {
for (int id : this.parent) {
System.out.print(id + " ");
}
System.out.println();
}
public static void main(String[] args) {
int n = 10;
UnionFind1 union = new UnionFind1(n);
System.out.println("初始：");
union.printArray();
System.out.println("连接了5 6");
union.unionElements(5, 6);
union.printArray();
System.out.println("连接了1 2");
union.unionElements(1, 2);
union.printArray();
System.out.println("连接了2 3");
union.unionElements(2, 3);
union.printArray();
System.out.println("连接了1 4");
union.unionElements(1, 4);
union.printArray();
System.out.println("连接了1 5");
union.unionElements(1, 5);
union.printArray();
System.out.println("1 6 是否连接：" + union.isConnected(1, 6));
System.out.println("1 8 是否连接：" + union.isConnected(1, 8));
}
}
快速合并
public class UnionFind2 {
private int[] parent;
private int size;
public UnionFind2(int size) { //初始化并查集
this.size = size;
parent = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i;
}
}
/**
* 查找element集合的头结点
* element=parent[element]:说明element元素是一个集合的头结点或者是自己一个集合
*
* @param element
* @return
*/
public int find(int element) {
while (element != parent[element]) {//此时说明element已不是自己一个结点了,所以通过循环找寻element所属集合的头结点
element = parent[element];
}
return element; //
}
/**
* 判断两个元素是否是一个集合:只需要判断两个元素所属集合的头结点是否相同即可
*
* @param firstElement
* @param secondElement
* @return
*/
public boolean isConnected(int firstElement, int secondElement) {
int firstUnion = find(firstElement);
int secondUnion = find(secondElement);
return firstUnion == secondUnion;
}
/**
* 合并firstElement,secondElement所在的两个集合
* 将firstElement集合的头结点指向secondElement集合的头结点
*
* @param firstElement
* @param secondElement
*/
public void unionElements(int firstElement, int secondElement) {
int firstUnion = find(firstElement);
int secondUnion = find(secondElement);
if (firstUnion != secondUnion) {
parent[firstElement] = secondUnion;
}
}
/**
* 打印每个元素所属集合的小组号,即它的上一个结点号
*/
private void printArray() {
for (int parent : parent) {
System.out.print(parent + " ");
}
System.out.println();
}
public static void main(String[] args) {
int n = 10;
UnionFind2 union = new UnionFind2(n);
System.out.println("初始：");
union.printArray();
System.out.println("连接了5 6");
union.unionElements(5, 6);
union.printArray();
System.out.println("连接了1 2");
union.unionElements(1, 2);
union.printArray();
System.out.println("连接了2 3");
union.unionElements(2, 3);
union.printArray();
System.out.println("连接了1 4");
union.unionElements(1, 4);
union.printArray();
System.out.println("连接了1 5");
union.unionElements(1, 5);
union.printArray();
System.out.println("1 6 是否连接：" + union.isConnected(1, 6));
System.out.println("1 8 是否连接：" + union.isConnected(1, 8));
}
}
快速合并--weight
public class UnionFind3 {
private int[] parent;
private int[] weight;
private int size;
public UnionFind3(int size) {
this.parent = new int[size];
this.weight = new int[size];
this.size = size;
for (int i = 0; i < size; i++) {
this.parent[i] = i;
this.weight[i] = 1;
}
}
/**
* 查找元素所属集合的头结点
*
* @param element
* @return
*/
public int find(int element) {
while (element != parent[element]) {
element = parent[element];
}
return element;
}
/**
* 判断两个元素是否是一个集合
*
* @param firstElement
* @param secondElement
* @return
*/
public boolean isConnected(int firstElement, int secondElement) {
return find(firstElement) == find(secondElement);
}
public void unionElements(int firstElement, int secondElement) {
int firstRoot = find(firstElement);
int secondRoot = find(secondElement);
if (firstRoot == secondRoot) {//已经是同一个集合的元素就不用再合并了
return;
}
//集合的子元素多的头结点,合并之后仍然做头结点
if (weight[firstRoot] > weight[secondRoot]) {
parent[secondRoot] = firstRoot;
weight[firstRoot] += weight[secondRoot];
} else {
parent[firstRoot] = secondRoot;
weight[secondRoot] += weight[firstRoot];
}
}
/**
* 打印parent数组
*/
public void printArray(int[] arr) {
for (int parent : arr) {
System.out.print(parent + " ");
}
System.out.println();
}
public static void main(String[] args) {
int n = 10;
UnionFind3 union = new UnionFind3(n);
System.out.println("初始parent：");
union.printArray(union.parent);
System.out.println("初始weight：");
union.printArray(union.weight);
System.out.println("连接了5 6 之后的parent：");
union.unionElements(5, 6);
union.printArray(union.parent);
System.out.println("连接了5 6 之后的weight：");
union.printArray(union.weight);
System.out.println("连接了1 2 之后的parent：");
union.unionElements(1, 2);
union.printArray(union.parent);
System.out.println("连接了1 2 之后的weight：");
union.printArray(union.weight);
System.out.println("连接了2 3 之后的parent：");
union.unionElements(2, 3);
union.printArray(union.parent);
System.out.println("连接了2 3 之后的weight：");
union.printArray(union.weight);
System.out.println("连接了1 4 之后的parent：");
union.unionElements(1, 4);
union.printArray(union.parent);
System.out.println("连接了1 4 之后的weight：");
union.printArray(union.weight);
System.out.println("连接了1 5 之后的parent：");
union.unionElements(1, 5);
union.printArray(union.parent);
System.out.println("连接了1 5 之后的weight：");
union.printArray(union.weight);
System.out.println("1 6 是否连接：" + union.isConnected(1, 6));
System.out.println("1 8 是否连接：" + union.isConnected(1, 8));
}
}
快速合并--height
public class UnionFind4 {
private int[] parent;
private int[] height;
int size;
public UnionFind4(int size) {
this.size = size;
this.parent = new int[size];
this.height = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i;
height[i] = 1;
}
}
public int find(int element) {
while (element != parent[element]) {
element = parent[element];
}
return element;
}
public boolean isConnected(int firstElement, int secondElement) {
return find(firstElement) == find(secondElement);
}
public void unionElements(int firstElement, int secondElement) {
int firstRoot = find(firstElement);
int secondRoot = find(secondElement);
if (firstRoot == secondRoot) {
return;
}
if (height[firstRoot] > height[secondRoot]) {
parent[secondRoot] = firstRoot;
} else if (height[firstRoot] < height[secondRoot]) {
parent[firstRoot] = secondRoot;
} else {
parent[firstRoot] = secondRoot;
height[secondRoot] += 1;
}
}
private void printArray(int[] arr) {
for (int parent : arr) {
System.out.print(parent + " ");
}
System.out.println();
}
public static void main(String[] args) {
int n = 10;
UnionFind4 union = new UnionFind4(n);
System.out.println("初始parent：");
union.printArray(union.parent);
System.out.println("初始height：");
union.printArray(union.height);
System.out.println("连接了5 6 之后的parent：");
union.unionElements(5, 6);
union.printArray(union.parent);
System.out.println("连接了5 6 之后的height：");
union.printArray(union.height);
System.out.println("连接了1 2 之后的parent：");
union.unionElements(1, 2);
union.printArray(union.parent);
System.out.println("连接了1 2 之后的height：");
union.printArray(union.height);
System.out.println("连接了2 3 之后的parent：");
union.unionElements(2, 3);
union.printArray(union.parent);
System.out.println("连接了2 3 之后的height：");
union.printArray(union.height);
System.out.println("连接了1 4 之后的parent：");
union.unionElements(1, 4);
union.printArray(union.parent);
System.out.println("连接了1 4 之后的height：");
union.printArray(union.height);
System.out.println("连接了1 5 之后的parent：");
union.unionElements(1, 5);
union.printArray(union.parent);
System.out.println("连接了1 5 之后的height：");
union.printArray(union.height);
System.out.println("1 6 是否连接：" + union.isConnected(1, 6));
System.out.println("1 8 是否连接：" + union.isConnected(1, 8));
}
}
路径压缩
public class UnionFind5 {
private int[] parent;
private int[] height;
int size;
public UnionFind5(int size) {
this.size = size;
this.parent = new int[size];
this.height = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i;
height[i] = 1;
}
}
public int find(int element) {
while (element != parent[element]) {
parent[element]=parent[parent[element]];//对于height比较大的,可以压缩路径
element = parent[element];
}
return element;
}
public boolean isConnected(int firstElement, int secondElement) {
return find(firstElement) == find(secondElement);
}
public void unionElements(int firstElement, int secondElement) {
int firstRoot = find(firstElement);
int secondRoot = find(secondElement);
if (firstRoot == secondRoot) {
return;
}
if (height[firstRoot] > height[secondRoot]) {
parent[secondRoot] = firstRoot;
} else if (height[firstRoot] < height[secondRoot]) {
parent[firstRoot] = secondRoot;
} else {
parent[firstRoot] = secondRoot;
height[secondRoot] += 1;
}
}
private void printArray(int[] arr) {
for (int parent : arr) {
System.out.print(parent + " ");
}
System.out.println();
}
public static void main(String[] args) {
int n = 10;
UnionFind5 union = new UnionFind5(n);
System.out.println("初始parent：");
union.printArray(union.parent);
System.out.println("初始height：");
union.printArray(union.height);
System.out.println("连接了5 6 之后的parent：");
union.unionElements(5, 6);
union.printArray(union.parent);
System.out.println("连接了5 6 之后的height：");
union.printArray(union.height);
System.out.println("连接了1 2 之后的parent：");
union.unionElements(1, 2);
union.printArray(union.parent);
System.out.println("连接了1 2 之后的height：");
union.printArray(union.height);
System.out.println("连接了2 3 之后的parent：");
union.unionElements(2, 3);
union.printArray(union.parent);
System.out.println("连接了2 3 之后的height：");
union.printArray(union.height);
System.out.println("连接了1 4 之后的parent：");
union.unionElements(1, 4);
union.printArray(union.parent);
System.out.println("连接了1 4 之后的height：");
union.printArray(union.height);
System.out.println("连接了1 5 之后的parent：");
union.unionElements(1, 5);
union.printArray(union.parent);
System.out.println("连接了1 5 之后的height：");
union.printArray(union.height);
System.out.println("1 6 是否连接：" + union.isConnected(1, 6));
System.out.println("1 8 是否连接：" + union.isConnected(1, 8));
}
}
例题
例题:How Many Tables
public class Main {
private int[] parent;
private int[] weight;
private int size;
private int groups;
public Main(int size) {
this.size = size;
this.groups = size;
this.parent = new int[size];
this.weight = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i;
weight[i] = 1;
}
}
public int find(int element) {
while (element != parent[element]) {
element = parent[element];
}
return element;
}
public boolean isConnected(int firstElement, int secondElement) {
return find(firstElement) == find(secondElement);
}
public void unionElement(int firstElement, int secondElement) {
int firstRoot = find(firstElement);
int secondRoot = find(secondElement);
if (firstRoot == secondRoot) {
return;
}
if (weight[firstRoot] < weight[secondRoot]) {
parent[firstRoot] = secondRoot;
weight[secondRoot] += weight[firstRoot];
} else {
parent[secondRoot] = firstRoot;
weight[firstRoot] += weight[secondRoot];
}
this.groups--;
}
public int getGroups() {
return this.groups;
}
public void printArray(int[] arr) {
for (int parent : arr) {
System.out.print(parent + " ");
}
System.out.println();
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
for (int i = 0; i < n; i++) {
int N = scan.nextInt();
Main m = new Main(N);
int M = scan.nextInt();
for (int j = 0; j < M; j++) {
int a = scan.nextInt()-1;
int b = scan.nextInt()-1;
m.unionElement(a, b);
}
System.out.println(m.getGroups());
}
}
}
并查集
并查集--basicpublicclassUnionFind1{privateint[]parent;//数组,表示并查集所有元素的集合号privateintsize;//表示并查集元素个数publicUnionFind1(intsize){//并查集初始化this.size=size;parent=newint[size];for(inti=0;i<size;i++){parent[i]= 查看详情
并查集并查集
模板数组版：intparent[MAX_N];intrank[MAX_N];voidInit(intn){ for(inti=0;i<n;++i){ parent[i]=i; rank[i]=0; }}intFind(intx){ if(parent[x]=x){ returnx; }else{ returnFind(parent[x]); }}voidUnion(intx,inty 查看详情
并查集-----好忧伤的并查集
主要还是看find的join俩个操作,测试数据16124313566171#include<iostream>#include<stdio.h>#include<memory.h>usingnamespacestd;/***并查集判断有几个联通子图*/constintmaxN=20;inta[maxN];intfind(intkey);voidjoi 查看详情
数据结构----并查集(代码片段)
并查集并查集概念并查集的模拟实现模拟实现并查集优化Union优化压缩路径循环递归并查集例题并查集概念并查集在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个单元素集... 查看详情
并查集学习笔记
并查集是用来查询、合并的有力工具。并查集是用来查询、合并的有力工具。 查看详情
并查集
...立的元素通过某种方式相互合并为若干个集合的方法即为并查集。 intset[N];//并查集集合for(i=0;i<=N;i++)set[i]=i;//并查集初始化，每个元素自为一个集合intfind(inti){//并查集查找，某个元素为根代表这个集合intr=i;while(r!=set[r])r=set... 查看详情
并查集p3367模板并查集(代码片段)
P3367【模板】并查集#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>usingnamespacestd;intn,m,zi,xi,yi;intfather[10001] 查看详情
并查集原理分析(代码片段)
文章目录1.并查集是什么2.并查集性质3.并查集可以解决的问题4.并查集模板5.并查集的应用1.并查集是什么在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时**，每个元素自成一个单元素集合**... 查看详情
数据结构--并查集(代码片段)
并查集并查集原理并查集实现并查集原理在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个单元素集合，然后按一定的规律将归于同一组元素的集合合并。在此过程中要... 查看详情
并查集——新手学习记录(代码片段)
好吧，什么垃圾并查集，并查集什么的都是铁憨憨<+__+>现在开始复习回忆：（新手，有错误望指正）什么叫做并查集，并查集就是一个集合问题，其实最主要的就是知道并查集是一个求解集合数目的问题，具体的操作方法有... 查看详情
数据结构----并查集(代码片段)
并查集并查集概念并查集的模拟实现模拟实现并查集优化Union优化压缩路径循环递归(深度过深有栈溢出的风险)并查集例题并查集概念并查集在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每... 查看详情
并查集
带偏移量的并查集讲解Butterfly AC代码 第二种AC代码1182:食物链 AC代码 查看详情
并查集模板（洛谷——模板并查集）
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>usingnamespacestd;constintmaxn=10010;intfa[maxn],n,m;voidinit(){for(inti=1;i<=n;i++)fa[i]=i;}intfind(in 查看详情
libreoj#109.并查集
二次联通门:LibreOJ#109.并查集 /*LibreOJ#109.并查集并查集*/#include<cstdio>#defineMax4000090#defineMod998244353voidread(int&now){now=0;registercharword=getchar();while(word<‘0‘||w 查看详情
数据结构——并查集
一、并查集的定义 并查集是一种维护集合的数据结构，它的名字中“并”“查”“集”分别取自Union（合并）、Find（查找）、Set（集合）这3 个单词。也就是说，并查集支持下面两个操纵： 合并：合并两个集合。 ... 查看详情
并查集
-----------------siwuxie095 并查集基础 这里介绍并查集（UnionFind），它是一种很不一样的树形结构 查看详情
关于并查集的一切全在这里了(代码片段)
文章目录并查集初识「并查集」常用术语「并查集」基本思想「并查集」的两个实现方式QuickFind方式实现并查集QuickFind工作原理：代码实现与验证时间复杂度QuickUnion方式实现并查集QuickUnion的工作原理为什么QuickUnion比QuickFind... 查看详情
并查集2——带权并查集
路径压缩前面的并查集的复杂度实际上有些极端情况会很慢。比如树的结构正好是一条链，那么最坏情况下，每次查询的复杂度达到了 O(n)。路径压缩 的思想是，我们只关心每个结点的父结点，而并不太关心树的真正的... 查看详情