找到有几张连通图即可解决问题。
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 }
标签:parent,int,graph,查集,DFS,BFS,rooty,1005,find From: https://www.cnblogs.com/coderhrz/p/18521108