并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中，其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间（1～3秒）内计算出试题需要的结果，只能用并查集来描述。
案例：
// 并查集 import java.util.Scanner; public class Main{ static int tree[]; static int n; static int m; static int relationOne; static int relationTwo; public static int findFather(int node){ if(node!=tree[node]){ return tree[node]=findFather(tree[node]); } return node; } public static void main(String args[]){ Scanner reader=new Scanner(System.in); n=reader.nextInt(); m=reader.nextInt(); tree=new int[n+1]; relationOne=reader.nextInt(); relationTwo=reader.nextInt(); for(int i=1;i<=n;i++){ tree[i]=i; } for(int i=1;i<=m;i++){ int one=reader.nextInt(); int two=reader.nextInt(); int oneFather=findFather(one); int twoFather=findFather(two); if(oneFather!=twoFather){ //父结点不同 if(oneFather>twoFather){ //指向更大的结点 tree[two]=oneFather; }else{ tree[one]=twoFather; } } } int relationOneFather=findFather(relationOne); int relationTwoFather=findFather(relationTwo); if(relationOneFather==relationTwoFather){ System.out.println("YES"); }else{ System.out.println("NO"); } } }
原文：https://www.cnblogs.com/chiweiming/p/10702874.html