并查集的实现

代码求解

father数组： 每个集合元素往上的指针，下标对应节点编号，初始时每个节点指向自己。

size数组：记录每个集合的大小，初始时每个集合大小为1。

stack数组 ： 用于扁平化过程中收集沿途节点。

publicstaticintMAXN=1000001;publicstaticint[]father=newint[MAXN];publicstaticint[]size=newint[MAXN];publicstaticint[]stack=newint[MAXN];publicstaticintn;publicstaticvoidbuild(){for(inti=0;i<=n;i++){father[i]=i;size[i]=i;}}publicstaticintfind(inti){intsize=0;while(i!=father[i]){stack[size++]=i;i=father[i];}while(size>0){father[stack[--size]]=i;}returni;}publicstaticbooleanisSameSet(intx,inty){returnfind(x)==find(y);}publicstaticvoidunion(intx,inty){intfx=find(x);intfy=find(y);if(fx!=fy){if(size[fx]>=size[fy]){size[fx]+=size[fy];father[fy]=fx;}else{size[fy]+=size[fx];father[fx]=fy;}}}publicstaticvoidmain(String[]args)throwsIOException{BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));StreamTokenizerin=newStreamTokenizer(br);PrintWriterout=newPrintWriter(newOutputStreamWriter(System.out));while(in.nextToken()!=StreamTokenizer.TT_EOF){n=(int)in.nval;build();in.nextToken();intm=(int)in.nval;for(inti=0;i<m;i++){in.nextToken();intop=(int)in.nval;in.nextToken();intx=(int)in.nval;in.nextToken();inty=(int)in.nval;if(op==1){out.println(isSameSet(x,y)?"Yes":"No");}else{union(x,y);}}}out.flush();out.close();br.close();}