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個朋友圈。

參考解法（Java版）：<Q：316190672，歡迎交流> 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<Integer> list = new LinkedList<Integer>(); //插入操作多所以使用LinkedListboolean flag = true; //判斷循環條件是否終止，while停止標記b[0] = true; //從第一項開始，表示已經遍歷過，并加入集合所以設置為truewhile (flag) {list = new LinkedList<Integer>();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<b.length;i++){if(b[i] == false){return false;}}return true;} }

運行結果： [1, 5, 4, 8, 2, 3, 6] [9, 20] [98, 11, 77] [13, 76]
與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的【小米校招笔试】假如已知有n个人和m对好友关系（存于数字r）。如果两个人是直接或间接的好友（好友的好友的好友...），则认为他们属于同一个朋友圈，请写程序求出这n个人里一共有多少个朋友圈。的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。