做题发现并查集也称为不相交并集，主要用来判断判断关系用的。
举个最简单例子，就比如说，亲戚问题，假设有n个人，m个关系，之后来判断其中任意两个人是否是亲戚，这其中有很多种情况，比如说两者就是给出的直接亲戚关系中的一种，其次两者的确是亲戚，但是两者并不存在着直接的亲戚关系，而是通过某个人而产生的，比如说1与2,2与3，那么1与3也就用该是亲戚，第三种就是直接的，两者并不存在着直接或间接的亲戚关系。这里面就可以用到并查集的思想。
所谓并查集，那么他肯定是分为两部分的，一部分就是查，这里的查就是查出该节点的最大的父亲节点，之后就是并，这里并的主要就是两者之间存在存在着关系的，主要先通过查去两个节点的最大的父亲节点，如果两者的父亲节点不相同的话那么就说明两者不是同一个集合，否则就是同一个集合。
我们一般就是通过数组来存取各个节点的情况。如下：
int []check=new int [n]; for(int i=0;i<n;i++) check[i]=i;
因为初始化的时候没有加入任何的关系，所以每个节点的父亲节点就是他本身
之后我们就来写并查集的两个函数，这里有两种写法如下：
方法一：
法一我们用来判断父亲节点主要是用过check[x]是否=x来判断
先写查这个函数，如下：
public static void Union(int x,int y) { if(find(x)!=find(y)) check[x]=check[y]; }
这里我们主要是通过输入的那个边，如果这两个点已经处在同一个集合中了，就不动，
否则就将这两个点并起来。
方法二：
法二我们用来判断父亲节点主要是通过check[x]是否<0来判断其是否是父节点
先讲查这个函数：
public static int find(int x) { if(check[x]<0) return find(-check[x]); else return check[x]; }
方法同理
接下来就是并这个函数：
public static void union(int x,int y) { if(find(x)!=find(y)) check[y]=-x; }
这里也是同理
接下来就贴源代码了
方法一：
import java.util.Scanner; public class 并查集第一版 { public static int check[]; public static int find(int x) { if(check[x]<0) return find(-check[x]); else return check[x]; } public static void union(int x,int y) { if(find(x)!=find(y)) check[y]=-x; } public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int m=sc.nextInt(); check=new int [n+1]; for(int i=1;i<n+1;i++) check[i]=i; for(int i=0;i<m;i++) { int num1=sc.nextInt(); int num2=sc.nextInt(); union(num1, num2); } int a1=sc.nextInt(); int a2=sc.nextInt(); if(find(a1)!=find(a2)) System.out.println("NO"); else System.out.println("YES"); } }
方法二：
import java.util.Scanner; public class 并查集第二版 { public static int check[]; public static int find(int x) { return (check[x]==x)?x:(check[x]=find(check[x])); } public static void Union(int x,int y) { if(find(x)!=find(y)) //check[x]=check[y]; check[find(x)]=find(y); } public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int m=sc.nextInt(); int []num1=new int [m]; int []num2=new int [m]; check=new int [n]; for(int i=0;i<n;i++) check[i]=i; for(int i=0;i<m;i++) { num1[i]=sc.nextInt()-1; num2[i]=sc.nextInt()-1; Union(num1[i], num2[i]); } int a1=sc.nextInt(); int a2=sc.nextInt(); if(find(a1-1)!=find(a2-1)) System.out.println("NO"); else System.out.println("YES"); } }
