思路:在博客园里,有对并查集思路的详解,模板神马的只是饭后甜点;
这儿有只野生模板君飘过,请各位OIer尽快捕捉
#include#include #include using namespace std;int n,m,x,y,fa[10000],v[10000],sum;int find(int x){ if(fa[x]!=x) return fa[x]=find(fa[x]); else return fa[x];}int unionn(int r1,int r2){ fa[r2]=r1;}int main(){ cin>>n>>m; for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=n;i++) { cin>>x>>y; int r1=find(x); int r2=find(y); if(r1!=r2) unionn(r1,r2); } //操作 <1>: /*cin>>q; for(int i=1;i<=q;i++){ cin>>a>>b; if(find(a)==find(b)) cout<<"Yes"< : /*for(int i=1;i<=n;i++) v[find(i)]++; for(int i=1;i<=n;i++){ if(v[i]!=1){ sum++; } } cout<