并查集模板题 HDU1856 More is better

---

题解： 并查集模板，我卡了一会。。树的高度那里。 还是不够熟悉。 另外，这题直接cin会超时 ，需要加上一句开关。 耗时从1000+到234ms

---

#include<bits/stdc++.h> using namespace std; const int maxn=100010; int F[maxn]; int len[maxn]; int f(int x) { if(x==F[x]) return x; return F[x]=f(F[x]); } void Union(int x,int y) { x=f(x); y=f(y); if(x!=y) { //cout<<"process "<<x<<" "<<y<<endl; //cout<<"F["<<x<<"]="<<f(x)<<endl; //cout<<"F["<<y<<"]="<<f(y)<<endl; F[x]=y; //cout<<"F["<<x<<"]="<<F[x]<<endl; len[y]+=len[x]; //cout<<"len "<<y<<": "<<len[y]<<endl; } } inline bool same(int x,int y) { return f(x)==f(y); } void ini(int n) { for(int i=1;i<=n;++i) { F[i]=i; len[i]=1; } } int main() { std::ios::sync_with_stdio(false);//不加超时 int t; int n,m; while(cin>>t) { ini(maxn); int flen=0; for(int i=0;i<t;++i) { cin>>n>>m; flen=max(flen,n); flen=max(flen,m); Union(n,m); } int maxnum=1; for(int i=1;i<=flen;++i) if(len[i]>maxnum) maxnum=len[i]; cout<<maxnum<<endl; } return 0; }