计蒜客：修建大桥(并查集/DFS/BFS）

Coder何 / 2025-02-21 / 原文

找到有几张连通图即可解决问题。

DFS：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n, m;
 4 int graph[1005][1005] = {0};
 5 bool visited[1005] = {false};
 6 void dfs(int p) {
 7     if (visited[p]) {
 8         return;
 9     }
10     visited[p] = true;
11     for (int i = 1; i <= n; ++i) {
12         if (graph[p][i] == 1)
13             dfs(i);
14     }
15 }
16 int main() {
17     cin >> n >> m;
18     while (m--) {
19         int s, e;
20         cin >> s >> e;
21         graph[s][e] = 1;
22         graph[e][s] = 1;
23     }
24     int cnt = 0;
25     dfs(1);
26     while(1) {
27         bool isconnected = true;
28         for (int i = 2; i <= n; ++i) {
29             if (!visited[i]) {
30                 isconnected = false;
31                 dfs(i);
32                 cnt++;
33                 break;
34             }
35         }
36         if (isconnected) {
37             cout << cnt;
38             break;
39         }
40     }
41 }

并查集：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n, m;
 4 vector<int> parent(1005);
 5 int find(int x) {
 6     if (parent[x] == x) {
 7         return x;
 8     }
 9     return find(parent[x]);
10 }
11 void merge(int x, int y) {
12     int rootx = find(x);
13     int rooty = find(y);
14     if (rootx != rooty) {
15         parent[rootx] = rooty;
16     }
17 }
18 
19 int main() {
20     cin >> n >> m;
21     for (int i = 1; i <= n; ++ i) {
22         parent[i] = i;
23     }
24     while (m--) {
25         int s, e;
26         cin >> s >> e;
27         merge(s, e);
28     }
29     set<int> roots;
30     for (int i = 1; i <= n; ++ i) {
31         roots.insert(find(i));
32     }
33     cout << roots.size() - 1;
34 }