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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;          // n 个顶点（1..n），m 条边
    cin >> n >> m;

    // adj[u] = 与 u 直接相连的顶点列表
    vector<vector<int>> adj(n + 1);  // 大小 n+1 以使用 1-indexed 顶点

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);  // 无向图：两个方向都要加
        adj[v].push_back(u);
    }

    // 遍历顶点 u 的所有邻居：O(deg(u))——最优
    for (int u = 1; u <= n; u++) {
        cout << u << " -> ";
        for (int v : adj[u]) cout << v << " ";
        cout << "\n";
    }

    return 0;
}

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

const int MAXV = 1001;

// 关键：声明为全局变量！
// 局部的 bool[1001][1001] 在栈上占 ~1 MB → 栈溢出崩溃。
// 全局变量存储在 BSS 段，自动初始化为零。
bool adj[MAXV][MAXV];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u][v] = true;   // 无向图：两个方向都要设置
        adj[v][u] = true;
    }

    // O(1) 边查询——邻接矩阵的杀手特性
    if (adj[2][3]) {
        cout << "边 2-3 存在\n";
    }

    return 0;
}

// 加权图的边结构体
struct Edge {
    int u, v, w;
    // 按权重升序排序：
    bool operator<(const Edge& other) const {
        return w < other.w;
    }
};

vector<Edge> edges;

// 读取输入：
for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    edges.push_back({u, v, w});
}

// 按权重排序——Kruskal MST 需要：
sort(edges.begin(), edges.end());

int n, m;
cin >> n >> m;
vector<vector<pair<int,int>>> adj(n + 1);
// adj[u] = {邻居, 权重} 对的列表
for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});  // 无向加权图
}

// C++17 结构化绑定遍历：
for (auto& [v, w] : adj[1]) {
    cout << "1 -> " << v << "（权重 " << w << "）\n";
}

int R, C;
cin >> R >> C;
vector<string> grid(R);
for (int r = 0; r < R; r++) cin >> grid[r];

// 4 方向：上、下、左、右
const int dr[] = {-1,  1,  0, 0};
const int dc[] = { 0,  0, -1, 1};

// 在单元格 (r, c) 处，遍历有效的可通行邻居：
auto neighbors = [&](int r, int c) {
    vector<pair<int,int>> result;
    for (int d = 0; d < 4; d++) {
        int nr = r + dr[d];
        int nc = c + dc[d];
        if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] != '#') {
            result.push_back({nr, nc});
        }
    }
    return result;
};

// 跳过自环（若题目中无意义）：
for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    if (u == v) continue;    // 自环：跳过
    adj[u].push_back(v);
    adj[v].push_back(u);
}

// 去除重边（只构建简单图）：
set<pair<int,int>> seen;
for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    if (u > v) swap(u, v);         // 规范化：始终 u < v
    if (seen.insert({u, v}).second) {
        // .second = true 意味着是新插入的（非重复）
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
}

int n;
cin >> n;
vector<vector<int>> adj(n + 1);
for (int i = 0; i < n - 1; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);   // 无向树边
}

vector<int> parent(n + 1, 0);
vector<int> depth(n + 1, 0);
vector<vector<int>> children(n + 1);

// 以节点 1 为根，用迭代 DFS（N 最大 10^5 时安全）
// 递归 DFS 对链（N = 10^5 深的路径）可能栈溢出
function<void(int, int)> rootTree = [&](int u, int par) {
    parent[u] = par;
    for (int v : adj[u]) {
        if (v != par) {                // v != par 避免向上回溯
            children[u].push_back(v);
            depth[v] = depth[u] + 1;
            rootTree(v, u);
        }
    }
};
rootTree(1, 0);   // 根 = 1，哨兵父节点 = 0

// 迭代 rootTree：BFS 顺序，任何树形状都安全
vector<int> order;
queue<int> bfsQ;
vector<bool> visited(n + 1, false);
bfsQ.push(1);
visited[1] = true;
parent[1] = 0;
depth[1] = 0;

while (!bfsQ.empty()) {
    int u = bfsQ.front(); bfsQ.pop();
    order.push_back(u);
    for (int v : adj[u]) {
        if (!visited[v]) {
            visited[v] = true;
            parent[v] = u;
            depth[v] = depth[u] + 1;
            children[u].push_back(v);
            bfsQ.push(v);
        }
    }
}
// order[] = BFS 遍历顺序（适用于自底向上 DP）

// 方式一：pair<int,int>——紧凑、常用
vector<vector<pair<int,int>>> adj(n + 1);
// adj[u] 存储 {v, w} 对

// 添加无向加权边 u–v，权重 w：
adj[u].push_back({v, w});
adj[v].push_back({u, w});

// 用 C++17 结构化绑定遍历：
for (auto& [v, w] : adj[u]) {
    cout << u << " -> " << v << "（代价 " << w << "）\n";
}

// 方式二：struct Edge——对复杂图更清晰
struct Edge {
    int to;       // 目标顶点
    int weight;   // 边代价
};
vector<vector<Edge>> adj(n + 1);

// 添加边：
adj[u].push_back({v, w});

// 遍历：
for (const Edge& e : adj[u]) {
    relax(u, e.to, e.weight);
}

维护 degree[] 数组。对每条边 (u, v)，做 degree[u]++ 和 degree[v]++。

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    vector<int> degree(n + 1, 0);

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        degree[u]++;
        degree[v]++;   // 无向图：两个端点各加 +1
    }

    for (int u = 1; u <= n; u++) {
        cout << degree[u];
        if (u < n) cout << " ";
    }
    cout << "\n";

    return 0;
}
// 时间：O(N + M)，空间：O(N)

对连通图：当且仅当 M = N − 1 时是树。不需要环检测——对连通图，边数本身就够了。

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;   // 读边（此题不需要用它们）
    }

    cout << (m == n - 1 ? "YES" : "NO") << "\n";
    return 0;
}
// 时间：O(M)，空间：O(1)

⚠️ 注意： 这只在图被保证连通时有效。对可能不连通的图，还需用 BFS/DFS 验证连通性（第 5.2 章）。有 N−1 条边的不连通图是森林（多棵树），不是单棵树。

构建有向邻接表（只加 adj[u].push_back(v)，不加反向边）。从 S 运行 BFS，若 T 被访问则输出 YES。

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, S, T;
    cin >> n >> m >> S >> T;

    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);   // 有向：只加一个方向
    }

    vector<bool> visited(n + 1, false);
    queue<int> q;
    visited[S] = true;
    q.push(S);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }

    cout << (visited[T] ? "YES" : "NO") << "\n";
    return 0;
}
// 时间：O(V + E)，空间：O(V + E)

若一个节点从未作为父节点出现，它就是叶节点。追踪 hasChild[u]，hasChild[u] = false 的节点就是叶节点。

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<bool> hasChild(n + 1, false);

    for (int i = 2; i <= n; i++) {
        int parent;
        cin >> parent;
        hasChild[parent] = true;   // 父节点至少有一个子节点
    }

    int leaves = 0;
    for (int u = 1; u <= n; u++) {
        if (!hasChild[u]) leaves++;
    }

    cout << leaves << "\n";
    return 0;
}
// 时间：O(N)，空间：O(N)

对每个可通行单元格，只检查其右和下邻居，避免重复计数。若两个单元格都可通行，计一条边。

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    vector<string> grid(n);
    for (int r = 0; r < n; r++) cin >> grid[r];

    int edges = 0;
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < m; c++) {
            if (grid[r][c] == '#') continue;
            // 检查右邻居
            if (c + 1 < m && grid[r][c+1] == '.') edges++;
            // 检查下邻居
            if (r + 1 < n && grid[r+1][c] == '.') edges++;
        }
    }

    cout << edges << "\n";
    return 0;
}
// 时间：O(N*M)，空间：O(N*M)

O(M) 构建邻接矩阵，每次查询 O(1)。展示了当 Q 大而 N 小时邻接矩阵优于邻接表（每次查询 O(deg)）的场景。

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

const int MAXV = 501;
bool adj[MAXV][MAXV];   // 全局：自动初始化为零，不会栈溢出

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u][v] = true;
        adj[v][u] = true;   // 无向图
    }

    int q;
    cin >> q;
    while (q--) {
        int a, b;
        cin >> a >> b;
        cout << (adj[a][b] ? 1 : 0) << "\n";   // 每次查询 O(1)！
    }

    return 0;
}
// 构建：O(M)，每次查询：O(1)，总计：O(M + Q)