小希的迷宫 Java代码 并查集算法

本文主要是介绍小希的迷宫 Java代码 并查集算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

小希的迷宫

题目

​ 小希设计了一个迷宫，首先她认为所有的通道都应该是双向连通的，就是说如果有一个通道连通了房间A和B，那么既可以通过它从房间A走到房间B，也可以通过它从房间B走到房间A，为了提高难度，小希希望任意两个房间有且仅有一条路径可以相通（除非走了回头路）。小希现在把她的设计图给你，让你帮忙判断她的设计图是否符合她的设计思路。比如下面的例子，前两个是符合条件的，但是最后一个却有两种方法从5到达8。

*Input*

输入包含多组数据，每组数据是一个以0 0结尾的整数对列表，表示了一条通道连接的两个房间的编号。房间的编号至少为1，且不超过100000。每两组数据之间有一个空行。
整个文件以两个-1结尾。

*Output*

对于输入的每一组数据，输出仅包括一行。如果该迷宫符合小希的思路，那么输出"Yes"，否则输出"No"。

*Sample Input*

6 8 5 3 5 2 6 4

5 6 0 0

8 1 7 3 6 2 8 9 7 5

7 4 7 8 7 6 0 0

3 8 6 8 6 4

5 3 5 6 5 2 0 0

-1 -1

*Sample Output*

Yes

Yes

No

分析：

使用并查集，箭头始终是从小指向大，重新分析图片：

代码

package lianxi;import java.util.Scanner;/*** @author* @date 2020/9/28 16:29* @description   小希的迷宫*/
public class xiaoxi {static  int[] a;public static void main(String[] args) {//初始化开辟空间a = new int[10000];Scanner s = new Scanner(System.in);while (true) {boolean flag = true;//初始化，使每一个变量的头就是它自己init();/*输入变量s1和s2，判断是否是（-1，-1）或者（0，0）* 如果是-1 -1，直接结束运行，* 如果是0 0，跳过，不做处理* 如果都不是以上的可能，就合并*/int s1 = s.nextInt();int s2 = s.nextInt();if(s1 == -1 && s2 == -1){break;}if (s1 == 0 && s2 == 0){continue;}merge(s1, s2);//接着录入其他数据for (int i = 0; i < a.length; i++) {int i1 = s.nextInt();int i2 = s.nextInt();//遇到0 0 结束录入if (i1 == 0 && i2 == 0) {break;}
/* 首先：题目中要求有且仅有一条路径可以相通，即，不能出现环路其次：并查集中合并方法（merge）使得箭头的方向永远是小头指向大头而，出现环路的条件就是：必有一个点的向外箭头数不为1，在进行判断环路的时候：判断两个点的头相等
所以判断两个数的头是不是同一个，把两个数链接起来，就会形成一个环路*/if (find(i1) != find(i2)) {merge(i1,i2);}else{flag = false;}}//再全部录入了数据以后判断flagif (flag){System.out.println("yes");}else{System.out.println("No");}}}//初始化public static  void  init(){for (int i = 1 ; i<a.length;i++){a[i] = i;}}//找头public static int find(int x){while (a[x] != x){x=a[x];}return x;}//合并public  static void merge(int x,int y){//先合并if (find(x) > find(y)){a[find(x)] = find(y);}if (find(x) < find(y)){a[find(y)] = find(x);}}
}

这篇关于小希的迷宫 Java代码 并查集算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---