部落中的最强战士题解

吴老师

2026-07-23 20:22:51

发布于：广东

9阅读

0回复

0点赞

部落中的最强战士

题目分析

题目中给出了若干名战士，以及战士之间的关系。

如果战士 $u$ 和战士 $v$ 属于同一个部落，那么可以在他们之间连接一条边。

由于同一个部落中的战士可以直接认识，也可以通过其他战士间接联系，因此：

一个部落就是无向图中的一个连通块。

例如存在下面的关系：

1 - 3 - 5

虽然战士 $1$ 和战士 $5$ 没有直接关系，但他们可以通过战士 $3$ 联系起来，所以三人属于同一个部落。

题目要求我们求出：

对于每一名战士，他所在连通块中的最大战斗力。

解题思路

我们可以使用 BFS 遍历每一个连通块。

对于每个还没有访问过的战士：

从这名战士开始进行 BFS。
找出所有和他属于同一个部落的战士。
在搜索过程中，记录这个部落中的最大战斗力。
BFS 结束后，把这个最大战斗力赋给部落中的每一名战士。

为什么需要记录部落中的所有战士

假设一个部落中有以下战士：

1 3 7 9

在 BFS 搜索过程中，我们一开始并不知道这个部落的最大战斗力是多少。

只有遍历完整个部落后，才能确定最大值。

因此，可以使用一个数组 members，记录当前部落中的所有战士编号。

搜索结束后，再统一填写答案。

BFS 搜索过程

假设当前从战士 start 开始搜索。

首先将他放入队列，并标记为已经访问：

queue<int> q;
q.push(start);
vis[start] = true;

然后不断取出队首战士：

int x = q.front();
q.pop();

对于所有和战士 x 有关系的战士 y：

如果 y 已经访问过，就跳过。
如果 y 没有访问过，就将其加入队列。

同时，我们还需要：

将 x 加入当前部落的成员数组。
更新当前部落的最大战斗力。

正确性说明

对于任意一个尚未访问的战士，我们从他开始进行 BFS。

BFS 会沿着所有关系不断向外搜索，因此：

所有与他直接相连的战士都会被找到。
所有能通过其他战士间接联系到他的战士也都会被找到。
不属于这个部落的战士无法通过关系到达，因此不会被加入。

所以，BFS 找到的战士恰好是当前部落中的所有战士。

在遍历这些战士时，我们不断更新最大战斗力，因此搜索结束后得到的就是该部落的最高战斗力。

最后将这个最大值赋给部落中的每一名战士，就能得到正确答案。

参考代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    // a[i] 表示第 i 名战士的战斗力
    vector<long long> a(n + 1);

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    // 邻接表存储战士之间的关系
    vector<vector<int>> graph(n + 1);

    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;

        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    // vis[i] 表示第 i 名战士是否已经访问过
    vector<bool> vis(n + 1, false);

    // ans[i] 表示第 i 名战士所在部落的最大战斗力
    vector<long long> ans(n + 1);

    for (int start = 1; start <= n; start++) {
        // 已经属于某个搜索过的部落，不需要再次搜索
        if (vis[start]) {
            continue;
        }

        queue<int> q;

        // 记录当前部落中的所有战士
        vector<int> members;

        // 当前部落的最大战斗力
        long long maxPower = a[start];

        q.push(start);
        vis[start] = true;

        while (!q.empty()) {
            int x = q.front();
            q.pop();

            members.push_back(x);
            maxPower = max(maxPower, a[x]);

            // 枚举所有与 x 有关系的战士
            for (int y : graph[x]) {
                if (vis[y]) {
                    continue;
                }

                vis[y] = true;
                q.push(y);
            }
        }

        // 将部落的最大战斗力赋给每一名部落成员
        for (int x : members) {
            ans[x] = maxPower;
        }
    }

    for (int i = 1; i <= n; i++) {
        cout << ans[i];

        if (i < n) {
            cout << ' ';
        }
    }

    cout << '\n';

    return 0;
}

样例解释

对于样例：

战士之间的关系为：

1 - 3

4 - 2 - 5

因此一共有两个部落。

第一个部落包含战士：

1 3

他们的战斗力分别为：

1 3

最大战斗力为：

所以战士 $1$ 和战士 $3$ 的答案都是 $3$ 。

第二个部落包含战士：

2 4 5

他们的战斗力分别为：

2 4 5

最大战斗力为：

所以战士 $2$ 、战士 $4$ 和战士 $5$ 的答案都是 $5$ 。

最终输出：

3 5 3 5 5

复杂度分析

每名战士只会进入队列一次，每条关系最多会被访问两次。

时间复杂度为：

$O(n+m)$

邻接表、访问数组和答案数组需要的空间复杂度为：

$O(n+m)$

能够通过本题中：

$n\leq 10^5,\quad m\leq 2\times 10^5$

的数据范围。

易错点

1. 这是无向关系

战士 $u$ 和战士 $v$ 属于同一个部落，关系是双向的，因此建图时必须写两次：

graph[u].push_back(v);
graph[v].push_back(u);

2. 加入队列时就要标记

正确写法：

vis[y] = true;
q.push(y);

不要等到出队时才标记，否则同一名战士可能被重复加入队列。

3. 可能存在没有任何关系的战士

当一名战士没有和其他人建立关系时，他自己也构成一个部落。

这个部落只有他一个人，因此答案就是他自己的战斗力。

4. 战斗力应使用 `long long`

虽然题目中的样例出现了 $10^9$ ，使用 int 通常也能存储，但使用 long long 更加稳妥。

5. 必须遍历所有战士

图中可能有多个互不相连的部落，所以不能只从战士 $1$ 开始搜索。

需要枚举每一名战士：

for (int start = 1; start <= n; start++)

每遇到一个没有访问过的战士，就从他开始搜索一个新的部落。

有帮助，赞一个

去预览

0/2000

这里空空如也