B3852(图)

题目要求对每个节点 （从 1 到 ），将其所有出边指向的节点 按照权值 从小到大排序，权值相同时按节点编号从小到大排序。然后依次输出每个节点 的出边指向的节点序列（按 从小到大输出）。

解题思路

1. 存储结构：使用邻接表（vector<vector<int>> edges）存储每个节点的出边。edges[u] 存储所有从 出发指向的节点 。
2. 排序规则：对于每个节点 ，对其邻接表 edges[u] 排序：
   • 首先比较节点 的权值 ，权值小的在前。
   • 若权值相同，则比较节点编号 ，编号小的在前。
3. 输出格式：
   • 每行对应一个节点 （从 1 到 ）。
   • 若节点 没有出边，输出空行。
   • 否则，按排序后的顺序输出节点编号，空格分隔，行末无多余空格。

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        vector<int> w(n + 1);
        for (int i = 1; i <= n; i++) {
            cin >> w[i];
        }
        
        vector<vector<int>> edges(n + 1);
        for (int i = 0; i < m; i++) {
            int u, v;
            cin >> u >> v;
            edges[u].push_back(v);
        }
        
        // 对每个节点的出边列表排序
        for (int u = 1; u <= n; u++) {
            sort(edges[u].begin(), edges[u].end(), [&](int a, int b) {
                if (w[a] != w[b]) {
                    return w[a] < w[b];
                }
                return a < b;
            });
        }
        
        // 输出结果
        for (int u = 1; u <= n; u++) {
            if (edges[u].empty()) {
                cout << "\n";
                continue;
            }
            for (int i = 0; i < edges[u].size(); i++) {
                if (i > 0) cout << " ";
                cout << edges[u][i];
            }
            cout << "\n";
        }
    }
    return 0;
}

算法复杂度分析

• 时间复杂度：

  • 构建邻接表：
  • 排序操作：设节点 的出度为 ，排序单个邻接表耗时
  • 总排序时间：
    • 最坏情况（完全图）：，总时间
    • 一般情况（稀疏图）：（平均出度），总时间
  • 总时间复杂度：（ 通常主导）
  • 组数据总时间：

• 空间复杂度：

  • 存储权值数组：
  • 邻接表：
  • 总空间复杂度：