java最简单的并查集(不想交集合)以及杭电1272
【摘要】 并查集要有的一些属性: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)