洛谷 B3643 图的存储

// ✗ B3643 第一版：vector 存图，邻居**按输入顺序**输出。
//
// 这是绝大多数人真实的第一版 —— 三行建图、两个循环输出，看着毫无破绽。
// 而它错在题面那半句话上：「**再按照从小到大的顺序**，依次输出与顶点 i 直接相连的所有顶点」。
//
// vector 里邻居的顺序 = **边在输入里出现的顺序**，和「从小到大」没有任何关系。
// ⚠ 官方样例挡不住它（那组样例里每个点的邻居恰好就是升序进来的）—— 见解析页第 ① 步。

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

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

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<vector<int>> g(n + 1);
    vector<vector<int>> a(n + 1, vector<int>(n + 1, 0));

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
        a[u][v] = a[v][u] = 1;
    }

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) cout << a[i][j] << (j == n ? '\n' : ' ');

    for (int i = 1; i <= n; i++) {
        cout << g[i].size();
        for (int v : g[i]) cout << ' ' << v;        // ★ 没排序：这里是输入顺序
        cout << '\n';
    }
    return 0;
}

// ✗ B3643 第二版：链式前向星，邻居**倒序**出来。
//
// 换成本章第 4 步那份前向星，第一版那个「顺序不对」的毛病不但没好，还换了个方向：
// `add()` 把新边挂到链子**最前面** ⇒ 遍历 head 链拿到的邻居是**加边顺序的倒序**。
//
// ★ 这一版存在的意义，就是把「顺序错」这件事和「哪一种存法」拆开：
//   它和第一版**都是 WA，可是打出来的两行数字不一样** —— 顺序不是存法的属性，
//   是「你没管它」的后果。

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

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

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<int> head(n + 1, -1), to(2 * m), nxt(2 * m);
    vector<vector<int>> a(n + 1, vector<int>(n + 1, 0));
    int cnt = 0;
    auto add = [&](int u, int v) { to[cnt] = v; nxt[cnt] = head[u]; head[u] = cnt++; };

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        add(u, v);
        add(v, u);
        a[u][v] = a[v][u] = 1;
    }

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) cout << a[i][j] << (j == n ? '\n' : ' ');

    for (int i = 1; i <= n; i++) {
        int deg = 0;
        for (int e = head[i]; e != -1; e = nxt[e]) deg++;
        cout << deg;
        for (int e = head[i]; e != -1; e = nxt[e]) cout << ' ' << to[e];   // ★ 倒序
        cout << '\n';
    }
    return 0;
}

// ★ B3643 第三版：vector 存图 + 每个点的邻居 sort 一遍 —— **这一版就已经能 AC 了**。
//
// 顺着第一版的病往下改，一行就够：输出前把 g[i] 排一遍。
// 复杂度 O(n² + m log m)（n² 是输出矩阵本身要的，躲不掉）。
//
// ⚠ 别被「还能更快」吓住：顶格 n = 1000、m = 10⁵，
//   排序那部分只有 2m log(2m) ≈ 4 × 10⁶ 次比较，而输出矩阵本身就有 10⁶ 个数字。
//   **排序不是这道题的瓶颈，输出才是。**（解析页第 ④ 步量了这件事。）

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

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

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<vector<int>> g(n + 1);
    vector<vector<char>> a(n + 1, vector<char>(n + 1, 0));

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
        a[u][v] = a[v][u] = 1;
    }

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) cout << (int)a[i][j] << (j == n ? '\n' : ' ');

    for (int i = 1; i <= n; i++) {
        sort(g[i].begin(), g[i].end());              // ★ 补上的就是这一行
        cout << g[i].size();
        for (int v : g[i]) cout << ' ' << v;
        cout << '\n';
    }
    return 0;
}

// ★★ B3643 正解：一次 sort 都不用 —— 因为**第一问的答案里就藏着第二问要的顺序**。
//
// 题目让我们输出邻接矩阵。而邻接矩阵的第 i 行，天生就是「i 的所有邻居**按编号从小到大**」：
// 从左到右扫一遍 a[i][1..n]，遇到 1 就打印列号，出来的顺序**必然是升序的**。
//
//     for (int j = 1; j <= n; j++) if (a[i][j]) { deg++; nb.push_back(j); }
//
// ⇒ 两问用同一张矩阵、同一个扫描方向，`sort` 一次都不用，vector 邻接表也不用建。
//
// ★★ 这是第 29 章那句话最干净的一次现场：**存法没有绝对的好坏，只有配不配得上你要问的问题。**
//   题目问「按编号升序列出邻居」—— 邻接矩阵是**唯一一种天然就按这个顺序存着**的存法。
//   （前向星倒序、vector 输入序，两个都得额外做一步。）
//
// 复杂度 O(n² + m)，顶格 n = 1000 就是 10⁶ 次扫描 —— 和「输出矩阵」这件事本来就要花的一样多。
// 内存：`vector<char>` 的 n² 矩阵顶格 1 MB（题面给 256 MB）。

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

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

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<vector<char>> a(n + 1, vector<char>(n + 1, 0));

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        a[u][v] = a[v][u] = 1;                       // 题面保证无重边无自环
    }

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) cout << (int)a[i][j] << (j == n ? '\n' : ' ');

    for (int i = 1; i <= n; i++) {
        int deg = 0;
        for (int j = 1; j <= n; j++) deg += a[i][j];
        cout << deg;
        for (int j = 1; j <= n; j++) if (a[i][j]) cout << ' ' << j;   // ★ 天然升序
        cout << '\n';
    }
    return 0;
}