做题感悟:这题是并查集按个数合并的运用。
解题思路:只要将父亲节点存整个树的节点数,并且每次更新最大值就可以了(ps: n==0 时输出 1)。具体讲解见:
代码:
#include<stdio.h> #include<iostream> #include<map> #include<stack> #include<string> #include<string.h> #include<stdlib.h> #include<math.h> #include<vector> #include<queue> #include<algorithm> using namespace std ; #define LEN sizeof(struct node) const double PI = 3.1415926 ; const double INF = 99999999 ; const int MX =10000005 ; int father[MX] ; int find(int x) // 路径压缩 { return father[x] < 0 ? x : father[x]=find(father[x]) ; } int main() { int n ; while(~scanf("%d",&n)) { for(int i=1 ;i<=10000000 ;i++) father[i]=-1 ; int best=-1,ax,ay,x,y ; for(int i=0 ;i<n ;i++) { scanf("%d%d",&x,&y) ; ax=find(x) ; ay=find(y) ; if(ax!=ay) { if(father[ax]<father[ay]) { father[ax]+=father[ay] ; father[ay]=ax ; best = father[ax] < best ? father[ax] : best ; } else { father[ay]+=father[ax] ; father[ax]=ay ; best = father[ay] < best ? father[ay] : best ; } } } printf("%d\n",-best) ; } return 0 ; }