并查集求朋友圈最大人数

问题:
某学校有N个学生,形成M个俱乐部。每个俱乐部里的学生有着一定相似的兴趣爱好,形成一个朋友圈。一个学生可以同时属于若干个不同的俱乐部。根据“我的朋友的朋友也是我的朋友”这个推论可以得出,如果A和B是朋友,且B和C是朋友,则A和C也是朋友。请编写程序计算最大朋友圈中有多少人。
链接: https://pta.patest.cn/pta/test/15/exam/4/question/840
用并查集保存每个数据的根节点,最后用桶排序的方法输出相同根节点出现最多的次数。
PAT上的基础题为什么最后的case是错误的。
代码如下
#include <iostream>
#include <stdlib.h>

using namespace std ;

int  findRoot(  int set[    ],   int s  )
{
	if (s == set[s])  return s ;
	else 
	set[s] = findRoot( set , set[s] ) ;//把s的父节点set[s]赋给s继续寻找根节点,直到s==set[s]
		
	return set[s] ;
}

void  merge(  int set[ ] , int s1, int  s2  )
{
	int r1, r2;
	r1 = findRoot( set  ,  s1 ) ;
	r2 = findRoot(  set ,  s2 ) ;
	if (r1 != r2)
		set[r2] = r1 ;

}

int   main(    )
{
	int N, M ;   //N:学生总算  M:俱乐部总数
	int n  ;//俱乐部人数 
	int  set[30001 ] ;
	cin >> N >> M ;

	for (int i = 1; i <= N; ++i)
		set[i] = i ;

	for(  int i=1; i<=M;  ++i ){
		int student1 , student2;
		cin >> n ;
		cin >> student1 ;
		for  (  int j = 2; j<= n; ++j  ){
			cin >> student2 ;
			merge (  set , student1 , student2 ) ;
		}
	}

	
	for (int i = 1; i <= N; ++i)
		cout << set[ i ] << endl ;

	//桶排序
	int  sort[30001];
	for (int i = 1; i <= N; ++i)
		sort[i] = 0 ;
	int max = -1 ;
	for (int i = 1; i <= N; ++i)
	{
		++sort[set[i]] ;
		if ( sort[set[i]] > max   )
			max = sort[ set[i] ]  ;
	}

	cout << max << endl ;
	return 0 ;
} 
将最后的代码改为
for (int i = 1; i <= N; ++i)
{
++sort[findRoot(set, i)] ;
if (sort[findRoot(set, i)] > max   )
max = sort[findRoot(set, i)];
}
为什么这样就通过了,我已经把set[]数组保存每一个节点的根节点辣,findRoot(set, i),与 set[i]应该没有区别的啊

全部评论
set[r2] = r1 之后 你如果不执行findRoot(set,r2) 的话 是不会让set[r2]=findRoot(set,r2)的
点赞 回复 分享
发布于 2016-10-20 01:24
当然是不一样的, 你赋值是在findRoot中做的 set[s] = findRoot( set , set[s] ) ; 但是merge操作在findRoot后执行, 可能会改变root. 另外你这个赋值操作是一种并查集的优化方法, 称为路径压缩, 这样保证查找的路径不会过长, 复杂度为log级, 但并不能保证所有点都直接指向父节点, 否则查找就是稳定O(1)了. 实际上要达到近似常数的复杂度还需要使用按秩合并优化.
点赞 回复 分享
发布于 2016-10-20 01:59
而且你把代码发在这儿估计没有人会仔细看的吧。。
点赞 回复 分享
发布于 2016-10-20 01:24
set[findRoot(set,r2)]=findRoot(set,r1) 要这么写
点赞 回复 分享
发布于 2016-10-20 01:25
时间复杂度大概是多少?可以O(n)的做法吗
点赞 回复 分享
发布于 2020-03-30 09:28

相关推荐

10-09 00:50
已编辑
长江大学 算法工程师
不期而遇的夏天:1.同学你面试评价不错,概率很大,请耐心等待;2.你的排名比较靠前,不要担心,耐心等待;3.问题不大,正在审批,不要着急签其他公司,等等我们!4.预计9月中下旬,安心过节;5.下周会有结果,请耐心等待下;6.可能国庆节前后,一有结果我马上通知你;7.预计10月中旬,再坚持一下;8.正在走流程,就这两天了;9.同学,结果我也不知道,你如果查到了也告诉我一声;10.同学你出线不明朗,建议签其他公司保底!11.同学你找了哪些公司,我也在找工作。
点赞 评论 收藏
分享
点赞 9 评论
分享
牛客网
牛客企业服务