P2097 求咋写DFS

Zjy_AK_IOI @ 2024-11-26 21:28:07

by Diary_Of_Young @ 2024-11-27 10:10:27

不应该用并查集嘛

by Zjy_AK_IOI @ 2024-11-27 17:58:24

@Diary_Of_Young为啥不可以DFS

by Diary_Of_Young @ 2024-11-27 18:01:39

一般的，并查集的时间复杂度是看作常数级别，DFS是指数级的

by Diary_Of_Young @ 2024-11-27 18:02:55

你这题 n <= 100000 ， 会T掉

by Zjy_AK_IOI @ 2024-11-27 18:03:11

@Diary_Of_Young我才绿名,放过我吧

by Diary_Of_Young @ 2024-11-27 18:05:10

#include <bits/stdc++.h>
using namespace std;

// 定义数组大小上限
const int N = 100010;

// 全局变量声明
int m, n;  // m表示边的数量，n表示节点的数量
int f[N];  // 并查集数组，用于存储每个节点的父节点信息
int x, y;  // 用于临时存储输入的边的两个端点
int cnt;   // 用于统计最终独立组（连通分量）的数量

// 查找函数，用于找到节点x所在集合的代表元素（根节点）
int find(int x) {
    if (f[x] == x) return x;
    // 路径压缩，优化后续查找操作
    return f[x] = find(f[x]);
}

// 合并函数，用于合并包含节点x和节点y的两个集合
void add(int x, int y) {
    f[find(y)] = find(x);
}

int main() {
    // 读取节点数量n和边的数量m
    cin >> n >> m;

    // 初始化并查集数组，每个节点的父节点初始设为自己
    for (int i = 1; i <= n; i++)
        f[i] = i;

    // 根据输入的边信息，依次合并相应节点所在的集合
    for (int i = 1; i <= m; i++) {
        cin >> x >> y;
        add(x, y);
    }

    // 统计最终独立组（连通分量）的数量，即根节点的数量
    for (int i = 1; i <= n; i++)
        if (f[i] == i) cnt++;

    // 输出独立组（连通分量）的数量
    cout << cnt;

    return 0;
}

by Diary_Of_Young @ 2024-11-27 18:06:19

其实不难

by Super_Yang @ 2024-11-27 21:05:40

DFS测评结果

并查集测评结果

题意明了，统计图上连通分量的个数

一般采用并查集（DFS当然也行）

思路 DFS统计连通分量的个数

双向建边，从1~n每个点遍历（若该点未访问）答案计数++ 并进行DFS把所有与他相连的边打上访问标记。

by Super_Yang @ 2024-11-27 21:08:56

@Diary_Of_Young DFS时间复杂度也没那么高 本题能过

但是建边空间比并查集大

by Super_Yang @ 2024-11-27 21:12:42

@Zjy_AK_IOI DFS能过，但存边内存比并查集大很多