2016年小米校招筆試第三題（西安站）

3?假如已知有n個人和m對好友關系（存于數(shù)字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個朋友圈。

參考解法（c/c++版）：<Q：316190672，歡迎交流>
// 簡單的并查集應用 #include<stdio.h> #include<stdlib.h> int set[5];inline int find(int x) //帶路徑優(yōu)化的并查集查找算法 {int i, j, r;r = x;while (set[r] != r)r = set[r];i = x;while (i != r){j = set[i];set[i] = r;i = j;}return r; } inline void merge(int x, int y) //優(yōu)化的并查集歸并算法 {int t = find(x);int h = find(y);if (t < h)set[h] = t;elseset[t] = h; }int friends(int n, int m, int r[11][2]) {int i, count;for (i = 1; i <= n; ++i) //初始化并查集，各點為孤立點，分支數(shù)為n set[i] = i;for (i = 0; i < m; ++i)merge(r[i][0], r[i][1]);count = 0;for (i = 1; i <= n; ++i){if (set[i] == i)++count;}return count; }int main(void){/* int r[11][2] = { { 1, 5 }, { 3, 5 }, { 4, 5 }, { 1, 4 }, { 5, 6 }, { 8, 1 }, { 9, 20 }, { 98, 11 }, { 13, 76 }, { 98, 77 }, { 2, 1 } };*/int r[5][2] = { { 1, 2 }, { 2, 3 }, {4,5}};int i;for (i = 0; i < sizeof(r[5][2]) / sizeof(r[0]);i++){merge(r[i][0],r[i][1]);}printf("%d\n",friends(5, 3, r));system("PAUSE");return 0; }運行結果：

總結

以上是生活随笔為你收集整理的【小米笔试题】朋友圈问题-并查集解法的全部內容，希望文章能夠幫你解決所遇到的問題。

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