小米13笔试编程题 4

浏览数：126 / 时间：2015年06月11日

朋友圈（25分）
假如已知有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个朋友圈。
最后请分析所写代码的时间、空间复杂度。评分会参考代码的正确性和效率。
C/C++：
int friends(int n , int m , int* r[]);

Java:
int friends(int n , int m , int[][] r);

朋友圈是考察并查集的问题

实现方法

n用编号最小的元素标记所在集合；

n定义一个数组 set[1..n] ，其中set[i] 表示元素i 所在的集合；

1	2	3	4	5	6	7	8	9	10
1	2	1	4	2	6	1	6	2	2

不相交集合： {1,3,7}, {4}, {2,5,9,10}, {6,8}

实现代码

find1(x)

{

return set[x];

}

时间复杂度O(1);

Merge1(a,b)

{ i = min(a,b);

j = max(a,b);

for (k=1; k<=N; k++) {

if (set[k] == j)

set[k] = i;

}

时间复杂度O(N)

具体代码如下：

 1 #include<iostream>;
 2 using namespace std;
 3 
 4 int set[100];
 5 
 6 int find(int x){
 7     int r=x;
 8     while(set[r]!=r){
 9         r=set[r];
10         return r;
11     }
12 }
13 
14 void merge(int a,int b){
15     int c=find(a);
16     int d=find(b);
17     if(c<d)
18         set[d]=c;
19     else 
20         set[c]=d;
21 
22 }
23 
24   int friends(int n , int m , int *r[]){
25       int count=0;
26     for(int i=0;i<n;i++){
27         set[i]=i;
28     }
29     cout<<set[0]<<set[1]<<set[2]<<set[3]<<set[4]<<set[5]<<endl;
30     for (int i=0;i<m;i++){
31         merge((r[i][0]),(r[i][1]));
32     }
33         for(int j=1;j<=n;j++){
34             if(set[j]==j)
35                 count++;
36         }
37         cout<<set[0]<<set[1]<<set[2]<<set[3]<<set[4]<<set[5]<<endl;
38         cout<<count<<endl;
39         return count;
40     
41 }
42     int main(){
43     int a[][3]={{1,2},{2,3},{4,5}};
44     int *input[]={&a[0][0],&a[1][0],&a[2][0]};
45     friends(6,3,input);
46 }