当前位置：首页 > article >正文

星际旅行(去年蓝桥杯省赛b组-第7题)

article 2025/4/2 21:05:45

题目链接:

蓝桥账户中心

朋友分享给我一道题，我刚开始其实先用dfs写，但是直接就超时了(很大的一部分原因是截图中没有数据范围)

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e9+7;
vector<int> graph[MAXN]; 
bool visited[MAXN];    
int dfs(int node, int steps) {
    if (steps < 0) return 0;
    visited[node] = true;
    int count = 1; 
    for (int x : graph[node]) {
        if (!visited[x]) {
            count += dfs(x, steps - 1);
        }
    }
    return count;
}
int main() {
    int n, m, Q;
    cin >> n >> m >> Q;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    double totalNum = 0; 
    for (int i = 0; i < Q; i++) {
        int x, y;
        cin >> x >> y;
        fill(visited, visited + n + 1, false);  
        int num = dfs(x, y); 
        totalNum += num;
    }
    double res = totalNum / Q;
    cout << fixed << setprecision(2) << res << endl;
    return 0;
}

找到原题后,改成bfs就过了

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e9+7;
vector<int> graph[MAXN];
int visitTime[MAXN] = {0};
int curTimes = 0;
int bfs(int x, int y) {
    if (y < 0) return 0;
    curTimes++;
    queue<pair<int, int>> q;
    q.push({x, 0});
    visitTime[x] = curTimes;
    int count = 1;
    while (!q.empty()) {
        auto [u, d] = q.front();
        q.pop();
        if (d >= y) continue;
        for (int v : graph[u]) {
            if (visitTime[v] != curTimes) {
                visitTime[v] = curTimes;
                count++;
                q.push({v, d + 1});
            }
        }
    }
    return count;
}

int main() {
    int n, m, Q;
    cin >> n >> m >> Q;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    double totalNum = 0;
    for (int i = 0; i < Q; ++i) {
        int x, y;
        cin >> x >> y;
        totalNum += bfs(x, y);
    }
    double ex= totalNum / Q;
    cout << fixed << setprecision(2) << ex << endl;
    return 0;
}

我其实想分享的是如何在比赛中去分辨简单图论问题应该是用dfs还是bfs进行求解

蓝桥杯比较喜欢考bfs, 但是如果你平常喜欢刷力扣或者面试题的话，我建议你图论就用dfs, 这是因为面试题它比较喜欢考DP, 你对dfs理解很深刻的话, 对你刷DP题也是有帮助的

根据上面的数据范围进行分析, 我最初写的dfs代码时间复杂度在O(n*Q), 明显超时了，但是改成bfs，它的时间复杂度在O(Q * (平均k + 平均e))

简单解释一下:

在BFS中，单次查询的时间复杂度为 O(k + e)，其中：

k 是实际访问的节点数，对应队列操作的时间复杂度。

e 是实际遍历的边数，对应处理每个节点的邻居的时间复杂度

队列操作的时间复杂度（O(k)）
BFS使用队列管理待扩展的节点。每个节点最多入队一次、出队一次，总共有 k 个节点被访问。因此，队列的入队和出队操作的时间复杂度为 O(k)。

处理边的时间复杂度（O(e)）
对于每个访问的节点，需要遍历它的所有邻居（即连接的边）。假设节点 u 有 degree(u) 条边，则处理 u 的时间复杂度为 O(degree(u))。
所有被访问节点的边数总和为 e = Σdegree(u)（其中 u 是被访问的节点），因此处理所有边的时间复杂度为 O(e)

由于每条边最多被处理两次（双向），总体复杂度为 O(Q * (平均k + 平均e))

然后就有人问了，哪为啥O(Q*(k+e)) 没有超时啊, 如果图退化成类似于单链表的形式, k->n, e->m, 时间复杂度就变成了O(Q*(n+m))了, 那不还是超时了吗

其实是不会出现上述的极端情况的, 因为常见的图都是稀疏图

稀疏性判断:

稀疏图定义：边数 m 远小于完全图的边数 n(n−1)/2。

本题中，m≤5n，即平均每个节点的度数不超过 10（因为平均度数=2m/n≤10）。

结论：这是一个典型的稀疏图

其中n(n−1)/2这个边界是完全图, 就是指图中每对不同的顶点之间都恰有一条边相连的图。对于有 n 个顶点的完全图，其边数最大。

平均度数计算: 所有节点的度数之和/n。在无向图中，每条边连接两个节点，因此每条边在计算所有节点的度之和时会被计算两次。如果图中有 m 条边，那么所有节点的度之和为 2m

所以平均度数=2*m/n

查询的步数限制 yi

如果 yi较小（如yi≤10），BFS 每层扩展的节点数受限于图的稀疏性，k 和 e 会远小于 n 和 m。

如果 yi 较大（如yi≈n），BFS 可能覆盖整个连通分量，此时k≈n, e≈m