并查集求朋友圈最大人数
问题:
某学校有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]应该没有区别的啊