【并查集】并查集增加、合并、查询、判断 - 木东驿站 - Powered by MoodBlog

CONTENT

【并查集】并查集增加、合并、查询、判断

并查集算是一种十分常用的解题工具,一般采用树表实现,效率比较高。

下文给出JAVA下的并查集操作

import java.util.Scanner;
class BFset{
	public int data;
	public int parent;
	public int level;//等级 层数近似值
}
class BFsets{
	private BFset[] bfset;
	BFsets(int n){
		bfset = new BFset[n+1];//预留n位置
	}
	void addset(int n){
		bfset[n] = new BFset();
		bfset[n].data = n;
		bfset[n].level = 0;
		bfset[n].parent = n;
	}
	//查询元素所在的集合
	int findSet(int n){
		if(bfset[n].parent==n){
			return n;
		}else{
			return findSet(bfset[n].parent);
		}
	}
	//两个元素所在集合合并
	void unionSets(int a,int b){
		a = findSet(a);
		b = findSet(b);
		if(bfset[a].level>bfset[b].level){
			bfset[b].parent = a;
		}else if(bfset[a].level<bfset[b].level){
			bfset[a].parent = b;
		}
		else{
			bfset[a].parent = b;
			bfset[b].level++;
		}
	}
	//判断两个元素是否属于同一个集合
	void issame(int a,int b){
		if(findSet(a)==findSet(b)){
			System.out.println("YES");
		}else{
			System.out.println("NO");
		}
	}
}


个快快 2017年11月04日 天气 晴

REMARKS

© 2018 MoodBlog 0.2 个快快 作品 | 参考主题: mathilda by fuzzz. | 鲁ICP备16047814号