【小米笔试题】朋友圈问题-并查集解法

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

// 简单的并查集应用
#include
#include
int set[5];inline int find(int x)           //带路径优化的并查集查找算法
{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)     //优化的并查集归并算法
{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)    //初始化并查集，各点为孤立点，分支数为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;
}

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