【搜索】求联通块个数的几种解法(深搜、并查集)_如何快速求并查集联通块数量及元素数量

问题描述

• 在N * M 的由0、1构成的矩阵中，寻找由0构成的联通块。

解法一：深搜

//
// Created by xiaoyu on 2019/9/27.
//

#include <iostream>

using namespace std;
const int n = 3, m = 5;
int dir[4][2] = {{-1, 0},{1, 0}, {0, 1}, {0, -1}};
int vis[n][m];
int maps[n][m] = {
  0,1,0,0,1,
  0,0,1,1,1,
  1,0,1,1,0,
};
int valid(int x, int y) {
  return x >= 0 && x < n && y >= 0 && y < m && !vis[x][y] && maps[x][y] == 0;
}
void dfs(int x, int y) {
  for (int i = 0; i < 4; i++) {
    int nx = x + dir[i][0], ny = y + dir[i][1];
    if (valid(nx, ny)) {
      vis[nx][ny] = 1;
      dfs(nx, ny);
    }
  }
}
int main() {
  int cnt = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (!vis[i][j] && maps[i][j] == 0) {
        dfs(i, j);
        cnt++;
      }
    }
  }
  cout << cnt << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

解法二：并查集

//
// Created by xiaoyu on 2019/9/27.
//
#include <iostream>
#include <cmath>
using namespace std;
const int maxn = 100, n = 3, m = 5;
int pre[n * m];
int dir[4][2] = {{-1, 0}, {1, 0}, {0,  1}, {0, -1}};
int maps[3][5] = {
  0, 1, 0, 0, 1,
  0, 0, 1, 1, 1,
  1, 0, 1, 1, 0,
};
struct Node {
  int x, y;
} Point[n * m];

int find(int x) {
  return x == pre[x] ? x : pre[x] = find(pre[x]); //路径压缩
}

void Union(int x, int y) {
  int fx = find(x), fy = find(y);
  if (fx != fy) {
    pre[fx] = fy;
  }
}

int main() {
  int len = 0; //0的个数
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (maps[i][j] == 0) {
        Point[len++] = Node{i, j};
      }
    }
  }
  for (int i = 0; i < len; i++) {
    pre[i] = i; //初始化，每个点的祖先都是自己
  }
  for (int i = 0; i < len; i++) {
    int x = Point[i].x, y = Point[i].y;
    for (int j = i + 1; j < len; j++) {
      int nx = Point[j].x, ny = Point[j].y;
      if (abs(x - nx) + abs(y - ny) == 1) { //这样相邻的点可以合并
        Union(i, j);
      }
    }
  }
  int cnt = 0;
  for (int i = 0; i < len; i++) {
    if (i == find(i)) cnt++; //这样的点就是祖先节点
  }
  for (int i = 0; i < len; i++) cout << pre[i] << " ";
  cout << endl;
  cout << cnt << endl;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59