int pre[1000 ]; int find(int x) { int r=x; while ( pre[r] != r ) //返回根节点 r r=pre[r]; int i=x , j ; while( i != r ){ //路径压缩 j = pre[ i ]; pre[ i ]= r ; i=j; } return r ;
再次优化
为了代码的简洁与优雅,find函数其实可以再次进行优化:
1 2 3 4 5 6
int find(int x){ if(pre[x]!=x){ pre[x]=find(pre[x]); } return pre[x]; }