【小米校招笔试】假如已知有n个人和m对好友关系（存于数字r）。如果两个人是直接或间接的好友（好友的好友的好友...），则认为他们属于同一个朋友圈，请写程序求出这n个人里一共有多少个朋友圈。

2016年小米校招笔试第三题（西安站）

3 假如已知有n个人和m对好友关系（存于数字r）。如果两个人是直接或间接的好友（好友的好友的好友...），则认为他们属于同一个朋友圈，请写程序求出这n个人里一共有多少个朋友圈。
假如：n = 5，m = 3，r = {{1 , 2} , {2 , 3} , {4 , 5}}，表示有5个人，1和2是好友，2和3是好友，4和5是好友，则1、2、3属于一个朋友圈，4、5属于另一个朋友圈，结果为2个朋友圈。

package XiaoMi;import java.util.LinkedList;
import java.util.List;public class test17 {/******************************************************************************************@Author:guomutian911* 算法思想：每一对好友为一项，如{1,5},{3,7}，{2，5}为三项。第一项中1为项的左值，5为项的右值。* 用布尔数组b[]标记遍历过的项，因为while循环是跳跃进行的，如上述关系所示，第一项为{1,5}，因为* 第二项中无第一项中元素则跳跃至第三项。算法借助了两个集合：list放遍历过的元素，数组b放项标记。****************************************************************************************/public static void main(String[] args) {int[][] r = { { 1, 5 }, { 3, 5 }, { 4, 5 }, { 1, 4 }, { 5, 6 },{ 8, 1 }, { 9, 20 }, { 98, 11 }, { 13, 76 }, { 98, 77 },{2,1} };friends( r);}/*** 根据二维数组输出朋友圈* @param r 关系数组* @return void* */static void friends(int[][] r) {boolean[] b = new boolean[r.length]; //标志是否遍历过，并加入朋友圈集合中int s = r[0][0]; //从第一项左边开始遍历List list = new LinkedList(); //插入操作多所以使用LinkedListboolean flag = true; //判断循环条件是否终止，while停止标记b[0] = true; //从第一项开始，表示已经遍历过，并加入集合所以设置为truewhile (flag) {list = new LinkedList();list.add(s); //加入一项中的左或右值for (int j = 0; j < list.size(); j++) {int key = list.get(j); //从头遍历listfor (int i = 0; i < r.length; i++) {if (r[i][0] == key) { //从头遍历所有项，分别取其左右值同list中key值比较if (!list.contains(r[i][1])) { //list中有左边值，无右边值（若用set则不用判断）list.add(r[i][1]); //加入右边值}b[i] = true; //标记该项已遍历} else if (r[i][1] == key) { if (!list.contains(r[i][0])) { //list中有右边值，无左边值list.add(r[i][0]); }b[i] = true; //标记该项已遍历}}}System.out.println(list); //输出一条朋友圈//while循环为跳跃前进，所以需要对标记数组从头遍历for (int i = 0; i < b.length; i++) {if (b[i] == false) {s = r[i][0]; //如果没有遍历过，则定位到该处break; //结束for循环，继续上一步while循环}else if (i == b.length - 1&&allScan(b)) //使用短路与，减少复杂度flag = false; //停止while循环}}}/*** 判断一个boolean数组里面的值是不是全为true* @param b 接受的数组* @return boolean 如果数组全为true返回true* */static boolean allScan(boolean[] b){for(int i=0;i

[1, 5, 4, 8, 2, 3, 6]
[9, 20]
[98, 11, 77]
[13, 76]

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！