并查集求朋友圈最大人数
问题：
某学校有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]应该没有区别的啊
百威成长空间 50人发布