大学的同学来自全国各地，对于远离家乡步入陌生大学校园的大一新生来说，碰到老乡是多么激动的一件事，于是大家都热衷于问身边的同学是否与自己同乡，来自新疆的小赛尤其热衷。但是大家都不告诉小赛他们来自哪里，只是说与谁是不是同乡，从所给的信息中，你能告诉小赛有多少人确定是她的同乡吗？
|
输入
包含多组测试用例。 在接下来的M行里，每行包括3个整数，a，b, c，如果c为1，则代表a跟b是同乡；如果c为0，则代表a跟b不是同乡；
已知1表示小赛本人。 |
题目用每一行代表两人之间的老乡关系，这种方式和图中的表达很相似，我们可以通过深度优先搜索或是广度优先搜索来找到所有老乡。
广度优先搜索：
package bishi; import java.util.*; /** * @author ：dazhu * @date ：Created in 2020/3/29 18:20 * @description： * @modified By： * @version: $ */ public class Main { private static int n; private static int m; //m行3列记录 private static int[][] arr; //add尾部添加，poll头部取出 private static Queue<Integer> queue; private static int[] markArr; public static void main(String[]args) { Scanner sc = new Scanner(System.in); while(sc.hasNext()) { n = sc.nextInt(); m = sc.nextInt(); markArr = new int[n + 1]; // 本人标记为老乡，防止重复 markArr[1] = 1; queue = new LinkedList<Integer>(); //先将1号老乡入队列 queue.add(1); //m行3列记录 arr = new int[m][3]; for (int i = 0; i < m; i++) { for (int j = 0; j < 3; j++) { arr[i][j] = sc.nextInt(); } } System.out.println(bfs(arr)); } } //采用广度搜索来寻找老乡 //建立队列用来存放，当前已知的老乡编号。 //同时建立标记数组用来标记该编号是不是老乡，防止老乡重复进入队列 //不断在根据当前队列的老乡编号，来不断寻找新的老乡，同时pop出此时久老乡。 //知道队列中已无老乡 private static int bfs(int[][]arr){ //只要queue不为空 int temp = 0; int counter = 0; while(!queue.isEmpty()){ //从queue头部取出， temp = queue.poll(); //根据出去编号，查找该编号的老乡 for(int[]a:arr){ if(a[0]==temp && a[1]!=temp && a[2]==1 && markArr[a[1]]==0){ //将该老乡入队列 queue.add(a[1]); //同时标记该老乡 markArr[a[1]] = 1; counter++; } else{ if(a[1]==temp && a[0]!=temp && a[2]==1 && markArr[a[0]]==0){ //将该老乡入队列 queue.add(a[0]); //同时标记该老乡 markArr[a[0]] = 1; counter++; } } } } return counter; } }
原文：https://www.cnblogs.com/dazhu123/p/12655132.html