经典指数          
原因
2000
浏览数
0
收藏数
 

百度全体员工玩分组游戏,前面五分钟大家分头找队友,并将每个人找到的队友信息汇报给主持人,如果A和B是队友,B和C是队友,那么A和C也是队友;接着主持人不断地随机抽取两个人,希望判断二者是否为队友。请设计一个计算机程序辅助主持人判断两个人是否为队友,说明程序的关键算法,不需要代码实现。 例如: <小明,小王>,<小军,小王>,<小丽,小李>是队友,那么小军和小明是队友,小军和小丽不是队友。

     举报   纠错  
 
切换
1 个答案

可以用并查集来做,用集合中最小的元素来表示关联集合,设置两个数组A,B,A存储员工,B[i]表示员工A[i]的集合,若A[i]和A[j]是朋友,更新B[i]和B[j]为min{i,j}, 每次任意选取员工a1,a2。 判断其是否属于同一关联集合,

      int getSetId(int a){       int i = a;

      while(B[i]!=i){             i = B[i];       }      

return i;     }     bool isFriends(int a1,int a2){

           return getSetId(a1)==getSetId(a2);     }

 
切换
撰写答案