dfs and 并查集
- 森林中, 连通分量的个数 = 树的个数 = 节点个数 - 边的条数, 但是在==图中却不一定==, 因为图中可能存在环.
- 图的dfs
void dfs(int i) {
visited[i] = 1;
for (int j = 1; j <= N; j++) {
if (visited[j] == 0 && g[i][j] == 1) {
dfs(j);
}
}
}- 容器建立和赋值
#include <vector>
#include <algorithm>
vector<int> visited(1000, 0);
fill(visited.begin(), visited.end(), 0);- 并查集
#include <cctype>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <bitset>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
// #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxN = 1000 + 5;
int Tree[maxN];
struct w {
int x;
int y;
} way[maxN * maxN / 2];
int findRoot(int x) {
if (Tree[x] == -1) {
return x;
}
else {
Tree[x] = findRoot(Tree[x]);
return Tree[x];
}
}
int main() {
way[0].x = 1;
way[0].y = 2;
way[1].x = 1;
way[1].y = 3;
way[2].x = 4;
way[2].y = 5;
way[3].x = 4;
way[3].y = 6;
way[4].x = 5;
way[4].y = 6;
// 1
// / \
// 2 3
// 4
// / \
// 5---6
int N = 6;
int M = 5;
for (int i = 0; i <= N; i++) {
Tree[i] = -1;
}
for (int i = 0; i < M; i++) {
int rx = findRoot(way[i].x);
int ry = findRoot(way[i].y);
// cout << rx << " " << ry << endl;
if (rx != ry) {
Tree[rx] = ry;
}
}
for (int i = 1; i <= N; i++) {
cout << i << " ";
}
cout << endl;
for (int i = 1; i <= N; i++) {
cout << Tree[i] << " ";
}
cout << endl;
int group = 0;
for (int i = 0; i < N; i++) {
if (Tree[i] == -1) {
group++;
}
}
cout << group << endl;
/*
1 2 3 4 5 6
2 3 -1 5 6 -1
2
*/
return 0;
}- 方法1: dfs
#include <cctype>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <bitset>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
// #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxN = 1000 + 5;
int g[maxN][maxN] = { 0 };
vector<int> visited(maxN, 0);
int N, M, K;
void dfs(int i) {
visited[i] = 1;
for (int j = 1; j <= N; j++) {
if (visited[j] == 0 && g[i][j] == 1) {
dfs(j);
}
}
}
int main() {
cin >> N >> M >> K;
for (int i = 0; i < M; i++) {
int a, b;
cin >> a >> b;
g[a][b] = g[b][a] = 1;
}
/*
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
cout << g[i][j] << " ";
}
cout << endl;
}
// */
for (int k = 0; k < K; k++) {
int destroyed;
cin >> destroyed;
int num = 0;
fill(visited.begin(), visited.end(), 0);
visited[destroyed] = 1;
for (int i = 1; i <= N; i++) {
if (visited[i] == 0) {
num++;
dfs(i);
}
}
cout << num - 1 << endl;
}
return 0;
}- 方法2: 并查集
#include <cctype>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <bitset>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
// #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxN = 1000 + 5;
int Tree[maxN];
struct w {
int x;
int y;
} way[maxN * maxN / 2];
int findRoot(int x) {
if (Tree[x] == -1) return x;
else {
int tmp = findRoot(Tree[x]);
Tree[x] = tmp;
return tmp;
}
}
int main() {
int N, M, K;
scanf("%d%d%d", &N, &M, &K);
for (int i = 0; i < M; i++) {
scanf("%d%d", &way[i].x, &way[i].y);
}
for (int k = 0; k < K; k++) {
for (int i = 1; i <= N; i++) {
Tree[i] = -1;
}
int c;
scanf("%d", &c);
for (int i = 0; i < M; i++) {
if (way[i].x != c && way[i].y != c) {
int rx = findRoot(way[i].x);
int ry = findRoot(way[i].y);
if (rx != ry) {
Tree[rx] = ry;
}
}
}
int group = 0;
for (int i = 1; i <= N; i++) {
if (Tree[i] == -1) {
group++;
}
}
printf("%d\n", group - 2);
}
return 0;
}
/*
Sample Input:
3 2 3
1 2
1 3
1 2 3
Sample Output:
1
0
0
*/