java最简单的并查集(不想交集合)以及杭电1272

举报
bigsai 发表于 2021/02/03 02:43:57 2021/02/03
【摘要】 并查集要有的一些属性:value:表示当前值,指针:(不一定是指针)指向父节点。 还有一个属性number:表示该树存在的总个数。(也可以用深度表示)。我用小树插在大树上。 如果是普通数字表示的树,可以简化: 初始全部-1,-1表示指向自己,数组的值表示指向。你可能会问那么总数怎么表示,很简单,其实我们不需要知道所有节点的总数,只需要根节点的总数就可以了,正常情况下根节...

并查集要有的一些属性:value:表示当前值,指针:(不一定是指针)指向父节点。 还有一个属性number:表示该树存在的总个数。(也可以用深度表示)。我用小树插在大树上。
如果是普通数字表示的树,可以简化:
初始全部-1,-1表示指向自己,数组的值表示指向。你可能会问那么总数怎么表示,很简单,其实我们不需要知道所有节点的总数,只需要根节点的总数就可以了,正常情况下根节点的初始是-1,但是一旦插入数据,根节点 (-1),根节点用负数来表示这个总数,就不用另外开一个属性来表示了。
总结来说:初始为-1,合并之后保留大的做父节点。小根指向父节点,值传给父节点,父节点的值为总个数。
举个例子:
1,3合并。1并在3三上,a[3]=a[1] a[3].(a[3]的值为-1 (-1)),然后1和4合并。4树插在(1,3)树上,a(1,3树根) =a[4];其实就是-2-1=-3;然后a[4]指向(1,3)树的根。当然,你要先构造查找根的值,和查找根的序号函数,也比较容易,下面就看代码:

public class DisjointSet {
	static int tree[]=new int[100000];//假设有500个值
	public DisjointSet() 	{set(this.tree);}
	public DisjointSet(int tree[]) 
	{
		this.tree=tree;
		set(this.tree);
	}
	public void set(int a[])//初始化所有都是-1 有两个好处,这样他们指向-1说明是自己,第二,-1代表当前森林有-(-1)个
	{
		int l=a.length;
		for(int i=0;i<l;i  )
		{ a[i]=-1;
		}
	}
	public int search(int a)//返回头节点的数值
	{
		if(tree[a]>0)//说明是子节点
		{ return search(tree[a]);
		}
		else return a;
	}
	public int value(int a)//返回a所在树的大小(个数)
	{
		if(tree[a]>0)
		{ return value(tree[a]);
		}
		else return -tree[a];
	}
	public void union(int a,int b)//表示 a,b所在的树合并
	{
		int a1=search(a);//a根
		int b1=search(b);//b根
		if(a1==b1) {System.out.println(a "和" b "已经在一棵树上");}
		else {
		if(tree[a1]<tree[b1])//这个是负数,为了简单减少计算,不在调用value函数
		{ tree[a1] =tree[b1];//个数相加  注意是负数相加 tree[b1]=a1; //b树成为a的子树,直接指向a;
		}
		else
		{ tree[b1] =tree[a1];//个数相加  注意是负数相加 tree[a1]=b1; //b树成为a的子树,直接指向a;
		}
		}
	}
	public static void main(String[] args)
	{
		DisjointSet d=new DisjointSet();
		d.union(1,2);
		d.union(3,4);
		d.union(5,6);
		d.union(1,6); d.union(22,24);
		d.union(3,26);
		d.union(36,24);
	System.out.println(d.search(6));	//头
	System.out.println(d.value(6)); //大小
	System.out.println(d.search(22));	//头
	System.out.println(d.value(22)); //大小
	}

}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70

运行结果:

6
4
24
3

  
 
  • 1
  • 2
  • 3
  • 4

实战一个题目,杭电1272小希的迷宫,简单修改下代码:注意数组大小为100001以为所以。

import java.util.Scanner;
public class 杭电oj1722union {
	public static void main(String[] args)
	{
		DisjointSet j=new DisjointSet();
		Scanner sc=new Scanner(System.in);
		boolean bool=true;
		int number=0;
		int last=0;
		while(sc.hasNext())
		{ int a=sc.nextInt(); int b=sc.nextInt(); if(a==-1&&b==-1) {break;} else if(a==0&&b==0)//输出 { if(number==0||bool&&j.value(last)==number) { System.out.println("Yes"); } else { System.out.println("No"); } j=new DisjointSet(); number=0; last=0;bool=true; sc.nextLine(); } else if(bool) { if(j.value(a)==1) {number  ;} if(j.value(b)==1) {number  ;} bool=j.union(a, b);last=b;}
		}
	}	
}
class DisjointSet {
	static int tree[]=new int[100001];//假设有500个值
	public DisjointSet() 	{set(this.tree);}
	public DisjointSet(int tree[]) 
	{
		this.tree=tree;
		set(this.tree);
	}
	public void set(int a[])//初始化所有都是-1 有两个好处,这样他们指向-1说明是自己,第二,-1代表当前森林有-(-1)个
	{
		int l=a.length;
		for(int i=0;i<l;i  )
		{ a[i]=-1;
		}
	}
	public int search(int a)//返回头节点的数值
	{
		if(tree[a]>0)//说明是子节点
		{ return search(tree[a]);
		}
		else return a;
	}
	public int value(int a)//返回a所在树的大小(个数)
	{
		if(tree[a]>0)
		{ return value(tree[a]);
		}
		else return -tree[a];
	}
	public boolean union(int a,int b)//表示 a,b所在的树合并
	{
		int a1=search(a);//a根
		int b1=search(b);//b根
		if(a1==b1) {return false;}
		else {
		if(tree[a1]<tree[b1])//这个是负数,为了简单减少计算,不在调用value函数
		{ tree[a1] =tree[b1];//个数相加  注意是负数相加 tree[b1]=a1; //b树成为a的子树,直接指向a;
		}
		else
		{ tree[b1] =tree[a1];//个数相加  注意是负数相加 tree[a1]=b1; //b树成为a的子树,直接指向a;
		}
		}
		return true;
	}	
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90

文章来源: bigsai.blog.csdn.net,作者:Big sai,版权归原作者所有,如需转载,请联系作者。

原文链接:bigsai.blog.csdn.net/article/details/80331195

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。