HDU6380(2018年百度之星1001）并查集

标题 ## HDU6380(2018年百度之星1001） 并查集

这里写代码片 #include <cstdio> #include <cstring> #define N 200000+10 using namespace std; int bin[N*N]; int vex[N]; int t,n,m,k; int a,b; int _find(int x) { return (x==bin[x])?x:(bin[x]=_find(bin[x])); } int main(void) { while (~scanf("%d",&t)){ while (t--){ memset(vex,0,sizeof(vex)); for (int i=0;i<N*N;i++) bin[i] = i; scanf("%d%d%d",&n,&m,&k); while (m--){ scanf("%d%d",&a,&b); vex[a]++; vex[b]++; int fx = _find(a); int fy = _find(b); if (fx!=fy) bin[fx] = fy; } int _max = 0; for (int i=1;i<n;i++){ if (vex[i]>vex[_max]) _max = i; //选出最大度顶点 } for (int i=0;i<n;i++){ if (_find(i)!=_find(_max)){ vex[_max]++; //不连通加一 bin[_find(i)] = bin[_find(_max)]; //使不连通的图连通 } } vex[_max] += k; if (vex[_max]>(n-1)) printf("%d\n",n-1); else printf("%d\n",vex[_max]); } } return 0; }