首页 > 代码库 > 小米13笔试编程题 4

小米13笔试编程题 4

2024-07-14 13:14:33   222人阅读

朋友圈（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 所在的集合；
 

12345678910
1214261622
不相交集合： {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 }

 


联系
我们