讨论一道面试题--number of connected components# JobHunting - 待字闺中
x*0
1 楼
给定一个n*n的board里面是0或1.算出里面独立0group的数量。比如
0 0 1 1 1
0 1 1 1 0
1 1 1 1 0
1 0 1 1 1
1 1 1 1 1
我的两个想法：
第一个当然就是DFS，bfs也行。每次遇到0的时候，进行DFS，得到一个connected
component。在DFS的过程中，把当前这个connected component的label改成count,
count初始化为1。并且DFS之后，count++。伪代码如下：
void dfs(int[][n] board, int row, int col, int count){
...
}
numofcp(board) {
count = 1;
for i = 1 : n
for j = 1 : n
if (board[i][j] == 0) {
dfs(i, j, count);
++count;
}
end
end
return count;
}
因为DFS的过程中，我们得用一个二维visited数组来标示已经访问过的元素。而每一次
进行DFS之前，都必须初始化这个visited数组。这个算法的时间复杂就有两部分组成：
numofcp*n*n(初始化visited) + number of elements having value 0 (DFS)
大家觉得呢？ 似乎瓶颈反而在初始化visited数组这一部分。有什么更快的方法来标示
已访问过得元素这个问题吗？
方法2：
为了解释这个算法，我们先把board中的1换成-1。这样的预处理不是必须的。
two-pass algorithm
第一遍pass，从左上角往右下角扫描。同样初始化count = 1， 检查每个0的
neighbours。2种情况。 （1） 都是0或-1， 那么label当前元素为count (2) 如果
neighbours中有已经labeled，label 当前元素为其中较小的。
第二遍pass， 从右下角往左上角扫描。对于每个非-1的元素，检查neighbours的label
，如果有较小的，改变当前元素的label。
这样两遍之后，所有的connected component就已经被标示好了。在第二遍时，可以用
一个set来记录用了多少个label，这就是最后的结果。
大家帮忙看看，算法的正确性。以及更好的算法。
0 0 1 1 1
0 1 1 1 0
1 1 1 1 0
1 0 1 1 1
1 1 1 1 1
我的两个想法：
第一个当然就是DFS，bfs也行。每次遇到0的时候，进行DFS，得到一个connected
component。在DFS的过程中，把当前这个connected component的label改成count,
count初始化为1。并且DFS之后，count++。伪代码如下：
void dfs(int[][n] board, int row, int col, int count){
...
}
numofcp(board) {
count = 1;
for i = 1 : n
for j = 1 : n
if (board[i][j] == 0) {
dfs(i, j, count);
++count;
}
end
end
return count;
}
因为DFS的过程中，我们得用一个二维visited数组来标示已经访问过的元素。而每一次
进行DFS之前，都必须初始化这个visited数组。这个算法的时间复杂就有两部分组成：
numofcp*n*n(初始化visited) + number of elements having value 0 (DFS)
大家觉得呢？ 似乎瓶颈反而在初始化visited数组这一部分。有什么更快的方法来标示
已访问过得元素这个问题吗？
方法2：
为了解释这个算法，我们先把board中的1换成-1。这样的预处理不是必须的。
two-pass algorithm
第一遍pass，从左上角往右下角扫描。同样初始化count = 1， 检查每个0的
neighbours。2种情况。 （1） 都是0或-1， 那么label当前元素为count (2) 如果
neighbours中有已经labeled，label 当前元素为其中较小的。
第二遍pass， 从右下角往左上角扫描。对于每个非-1的元素，检查neighbours的label
，如果有较小的，改变当前元素的label。
这样两遍之后，所有的connected component就已经被标示好了。在第二遍时，可以用
一个set
大家帮忙看看，算法的正确性。以及更好的算法。
