nodejs 并查集

function UnionFind(row, col, idx){

var o = new Object();

o.array = new Array(row*col);

o.isRandom = new Array(row*col);

o.init = function(row, col, idx){

for (var i = 0; i < row*col; i++){

o.isRandom[i] = 0;

o.array[i] = i;

}

for (var i = 0; i < idx; i++){

var num = Math.round(Math.random()*row*col);

//console.log(num);

if (o.isRandom[num]) i--;

else {

o.isRandom[num] = 1;

if (num%row>0 && o.isRandom[num-1]) o.union(num, num-1);

if (num%row<row-1 && o.isRandom[num+1]) o.union(num, num+1);

if (num%row>0 && o.isRandom[num-row]) o.union(num, num-row);

if (num%row<col-1 && o.isRandom[num+row]) o.union(num, num+);

}

}

//console.log(uf.printArray(100,100));

};

o.root = function(i){

while (i != o.array[i]){

o.array[i] = o.array[o.array[i]];

i = o.array[i];

}

return i;

};

o.connected = function(p, q){

return o.root(p) == o.root(q);

};

o.union = function(p, q){

o.array[o.root(p)] = o.root(q);

};

o.percolation = function(row, col){

for (var i = 0; i < row; i++){

for (var j = 0; j < col; j++){

//console.log(o.printArray(20,20));

//console.log(o.connected(i, (row-1)*col+j));

if(o.connected(i, (row-1)*col+j)) return true;

}

}

return false;

};

o.printArray = function(row, col){

for (var i = 0; i < col; i++){

console.log(o.array.slice(i*row, (i+1)*row));

}

};

return o;

}

var uf = new UnionFind(100, 100, 1);

var j = 1;

//uf.init(100, 100, 1100);

//console.log(uf.printArray(100,100));

//uf.percolation(100, 100)

var sum = 0;

//console.log(uf.printArray(100,100));

for (var i = 0; i < 1000; i++){

var j = 1;

uf.init(100, 100, 1);

//console.log(uf.printArray(100, 100));

while(!uf.percolation(100, 100)){

uf.init(100, 100, j);

j = j+1;

}

sum += j;

console.log(j/10000);

}

console.log(sum/10000000);