萌新学习算法——并查集基础

并查集

在算法设计中，将一个集合和另外一个集合合并时，就会用到并查集。假如不用并查集，你可能会用到集合和列表来实现，这样会使代码看起来很复杂，而且执行效率不高，下面用洛谷的题目P3367 并查集.来举例子：

题目描述：

如题，现在有一个并查集，你需要完成合并和查询操作。

输入格式
第一行包含两个整数N、M，表示共有N个元素和M个操作。

接下来M行，每行包含三个整数Zi、Xi、Yi

当Zi=1时，将Xi与Yi所在的集合合并

当Zi=2时，输出Xi与Yi是否在同一集合内，是的话输出Y；否则话输出N

输出格式
如上，对于每一个Zi=2的操作，都有一行输出，每行包含一个大写字母，为Y或者N

代码（用集合和列表实现）

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;

public class Main {
	public static int n, m;
	public static boolean flag[];  //用来判断是否已经加入列表，初始状态false
	//利用ArrayList来存储不同的集合，用set来存储每个集合里面的元素
	public static ArrayList<HashSet<Integer>> als = new ArrayList<>(); 

	public static void union(int x, int y) {
		if(x==y) return ;
		if (!flag[x] && !flag[y]) { //x和y都没有在列表里面，需要将x和y加入列表，并保存到同一个集合
			HashSet<Integer> newset = new HashSet<>();
			newset.add(x);
			newset.add(y);
			flag[x] = true;
			flag[y] = true;
			als.add(newset);
		} else {
			if (flag[x] && flag[y]) {  //当x和y都在列表里面
				int s = 0, e = 0;
				//找出x所在列表的下标
				for (int i = 0; i < als.size(); i++)
					if (als.get(i).contains(x)) { 
						s = i;
						break;
					}
				//找出y所在列表的下标
				for (int i = 0; i < als.size(); i++) {
					if (als.get(i).contains(y)) {
						e = i;
						break;
					}
				}
				//若x和y的下标相同，则证明在同一个集合，不需要合并
				if(e==s)
					return;
				//利用迭代器来实现，对下标大的那个集合遍历，将元素逐一加入下标小的那个集合中
				if (e < s) {	
					Iterator<Integer> set = als.get(s).iterator();
					while (set.hasNext())
						als.get(e).add(set.next());
					//最后将大的那个集合从列表中移除
					als.remove(s);
				} else {
					Iterator<Integer> set = als.get(e).iterator();
					while (set.hasNext())
						als.get(s).add(set.next());
					//最后将大的那个集合从列表中移除
					als.remove(e);
				}
				
			}//若只有一个在列表里面，另外一个没有在列表里面 
			else if (flag[x]) { //若x在列表中				
				int i;
				//找出x所在集合的下标
				for (i = 0; i < als.size(); i++)
					if (als.get(i).contains(x))
						break;
				//将y加入x所在集合
				als.get(i).add(y);
				//并将y加入列表
				flag[y] = true;
			} else {//若y在列表中	
				int i;
				//找出y所在集合的下标
				for (i = 0; i < als.size(); i++)
					if (als.get(i).contains(y))
						break;
				//将x加入y所在集合
				als.get(i).add(x);
				//并将y加入列表
				flag[x] = true;
			}
		}
	}

	//判断是否在同一个集合
	public static boolean inSet(int x, int y) {
		for (int i = 0; i < als.size(); i++)
			if (als.get(i).contains(x)) {
				if(als.get(i).contains(y)) //若x和y在同一个集合里面，则返回true，否则返回false
					return true;
				else
					return false;
				}
		return true;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		String str[] = reader.readLine().split(" ");
		n = Integer.parseInt(str[0]);
		m = Integer.parseInt(str[1]);
		flag = new boolean[n + 1];
		int x, y, z;
		StringBuffer sb = new StringBuffer();
		for (int i = 0; i < m; i++) {
			str = reader.readLine().split(" ");
			z = Integer.parseInt(str[0]);
			x = Integer.parseInt(str[1]);
			y = Integer.parseInt(str[2]);
			if (z == 1)   
				union(x, y); 
			else {
				//若x==y 不用集合判断，若x或y不在列表里面，证明它自己作为一个集合
				//只有当flag[x] && flag[y] && inSet(x, y)为真时，才证明是同一个集合
				if (x==y||(flag[x] && flag[y] && inSet(x, y))) 
					sb.append("Y").append("\n");
				else
					sb.append("N").append("\n");
			}
		}
		System.out.println(sb);

	}
}

通过上面的代码，我们会发现特别麻烦，接下来我们引入并查集：这里介绍如何用它实现集合的合并和判断是否在同一个集合：

判断是否在同一个集合：

在这里我们先定义了一个find方法去查找x所在的集合的根节点，思想：保存每个集合的根节点，初始化为为-1（利用小于0来判读是否为根节点，后面的数值用来保存该集合有多少个点），其实就一个树状图，利用x集合保存的时它的父亲节点的父亲的下标，直到出现负数为根节点，再根据根节点判断是否为同一个集合，若根节点相同，则是同一个集合：

代码实现（未压缩的find方法）：

public static int find(int x)
	{
		while(data[x]<0) return x;
		return find(data[x]);
	}

在这里有一个提高效率的方法，我们可以在找的同时顺带保存根节点，当下次查找的时候直接找到根节点，不需要每次都递归去寻找。

代码实现（压缩的find方法）：

	public static int find(int x)
	{
		while(data[x]<0) return x;
		return data[x]=find(data[x]);
	}

接下来我们就可以利用find函数来实现查找两个数是否属于同一个集合。

work方法：

public static boolean work(int x,int y)
	{
		int a=find(x),b=find(y);
		if(a==b)
			return true;
		return false;		
	}

最后我们利用find方法来实现合并的union方法。

union方法：

	public static void union(int x,int y)
	{
		int a=find(x),b=find(y);
		if(a==b)
			return ;
		data[a]+=data[b];
		data[b]=a;
	}

完整代码：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static int n,m,z,x,y;
	public static int data[];
	
	public static int find(int x)
	{
		if(data[x]<0) return x;	
		return data[x]=find(data[x]); //返回的是每个元素的根节点
	}
	
	public static void union()
	{
		int a=find(x);
		int b=find(y);
		if(a==b) return ; //若同为一个根，则不需要合并
		data[a]+=data[b];  //因为同为负数，所以可以直接相加
		data[b]=a; //将a作为b的根节点 
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
		String str[]=reader.readLine().split(" ");
		n=Integer.parseInt(str[0]); m=Integer.parseInt(str[1]);
		data=new int[n+1];
		for(int i=1;i<=n;i++)
			data[i]=-1;
		StringBuffer sb=new StringBuffer();
		for(int i=0;i<m;i++)
		{
			str=reader.readLine().split(" ");
			z=Integer.parseInt(str[0]); x=Integer.parseInt(str[1]);
			y=Integer.parseInt(str[2]);
			if(z==1)
				union();
			else
			{
				if(find(x)==find(y))
					sb.append("Y").append("\n");
				else
					sb.append("N").append("\n");
			}
			
		}
		System.out.println(sb);
	}
}