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);
