大家好，欢迎来到IT知识分享网。
题目描述
思路分析
代码实现
package com.atguigu.disjointSet;
public class djset {
public static int VERTICES=6;
public static void initialise(int parent[]){
int i;
for (i = 0; i < VERTICES; i++) {
parent[i]=-1;
}
}
public static int find_root(int x,int parent[]){
int x_root=x;
while (parent[x_root]!=-1){
x_root=parent[x_root];
}
//出了循环说明已经找到父节点
return x_root;
}
/* 返回1表示union成功 合并成功，0表示合并失败 */
public static int union_vertices(int x,int y,int parent[]){
int x_root=find_root(x,parent);
int y_root=find_root(y,parent);
if(x_root==y_root){
//x,y的父节点相同
return 0;
}else {
parent[x_root]=y_root;
return 1;
}
}
public static void main(String[] args) {
int parent[]=new int[VERTICES];
int edges[][]={
{
0,1},{
1,2},{
1,3},
{
2,4},
{
3,4},{
2,5}};
initialise(parent);
int i;
for ( i = 0; i < edges.length; i++) {
int x=edges[i][0];
int y=edges[i][1];
if(union_vertices(x,y,parent)==0){
System.out.println("存在环");
return;
}
}
System.out.println("不存在环");
}
}
压缩路径
package com.atguigu.disjointSet;
public class djset {
public static int VERTICES=6;
public static void initialise(int parent[]){
int i;
for (i = 0; i < VERTICES; i++) {
parent[i]=-1;
}
}
public static int find_root(int x,int parent[]){
int x_root=x;
while (parent[x_root]!=-1){
x_root=parent[x_root];
}
//出了循环说明已经找到父节点
return x_root;
}
/* 返回1表示union成功 合并成功，0表示合并失败 */
public static int union_vertices(int x,int y,int parent[],int rank[]){
int x_root=find_root(x,parent);
int y_root=find_root(y,parent);
if(x_root==y_root){
//x,y的父节点相同
return 0;
}else {
if(rank[x_root]>rank[y_root]){
parent[y_root]=x_root;
}else if(rank[y_root]>rank[x_root]){
parent[x_root]=y_root;
}else {
parent[x_root]=y_root;
rank[y_root]++;
}
}
}
public static void main(String[] args) {
int parent[]=new int[VERTICES];
int rank[]=new int[VERTICES];
int edges[][]={
{
0,1},{
1,2},{
1,3},
{
2,4},
{
3,4},{
2,5}};
initialise(parent);
int i;
for ( i = 0; i < edges.length; i++) {
int x=edges[i][0];
int y=edges[i][1];
if(union_vertices(x,y,parent,rank)==0){
System.out.println("存在环");
return;
}
}
System.out.println("不存在环");
}
}
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/11093.html
