11 图论基础：存图 / DFS / BFS / 拓扑排序

#include <iostream>
using namespace std;
const int N = 1005;
int g[N][N];        // 邻接矩阵：g[i][j] = 边权，0 表示无边
int main() {
    int n, m; cin >> n >> m;          // n 个点，m 条边
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u][v] = w;                  // 有向边 u→v；无向图再加 g[v][u] = w
    }
    // 邻接矩阵的优势：判断任意两点是否相连 O(1)
    if (g[1][2]) cout << "有边" << endl;
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;
const int N = 100005;
struct Edge { int to, w; };   // 一条出边：终点 to、权值 w
vector<Edge> adj[N];          // 邻接表：adj[u] 存 u 的所有出边

int main() {
    int n, m; cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});      // u → v
        adj[v].push_back({u, w});      // 无向图再加反向边
    }
    // 遍历 u 的所有邻居
    for (auto &e : adj[1]) {
        cout << "1 -> " << e.to << " w=" << e.w << endl;
    }
    return 0;
}

#include <iostream>
using namespace std;
const int N = 100005;
struct E { int to, w, next; } edges[N * 2];   // 链式前向星：边数组
int head[N];               // head[u] 为 u 的第一条边在 edges 中的下标
int en = 1;                // 边计数，从 1 开始（0 表示"无"）

// 头插法加边：新边指向 u 原来的第一条边，再把自己设为第一条
void addEdge(int u, int v, int w) {
    edges[en] = {v, w, head[u]};
    head[u] = en++;
}
int main() {
    addEdge(1, 2, 5);
    addEdge(1, 3, 2);
    // 遍历 1 的所有出边：沿 next 链走
    for (int e = head[1]; e != 0; e = edges[e].next) {
        cout << "1 -> " << edges[e].to << " w=" << edges[e].w << endl;
    }
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;
const int N = 100005;
vector<int> adj[N];        // 邻接表
bool vis[N];               // 访问标记数组

// 图的深度优先搜索（DFS）：一路走到底再回头
void dfs(int u) {
    vis[u] = true;                  // 先标记，防止重复访问
    cout << u << " ";
    for (int v : adj[u]) {          // 遍历邻居
        if (!vis[v]) dfs(v);        // 没访问过就递归
    }
}

int main() {
    int n, m; cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);        // 无向图双向建边
        adj[v].push_back(u);
    }
    dfs(1);                         // 从节点 1 开始
    cout << endl;
    return 0;
}

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N = 100005;
vector<int> adj[N];
int dist[N];                 // 到起点的距离（边权为 1 时即"最少步数"）

// 广度优先搜索（BFS）：按层扩展，第一次到达即最短距离
void bfs(int s) {
    fill(dist, dist + N, -1);      // -1 表示未访问
    queue<int> q;
    q.push(s);
    dist[s] = 0;                   // 起点距离 0
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {       // 第一次访问
                dist[v] = dist[u] + 1; // 距离 = 父距离 + 1
                q.push(v);
            }
        }
    }
}
int main() {
    int n, m; cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v); adj[v].push_back(u);
    }
    bfs(1);
    for (int i = 1; i <= n; i++) cout << dist[i] << " ";
    cout << endl;   // 输出到 1 的距离，-1 表示不可达
    return 0;
}

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N = 100005;
vector<int> adj[N];        // 邻接表（有向图）
int indeg[N];              // indeg[u]：节点 u 的入度（被指向次数）

// 拓扑排序：给 DAG 排出一个合法先后顺序
int main() {
    int n, m; cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        indeg[v]++;                 // 统计入度
    }
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (indeg[i] == 0) q.push(i);   // 入度为 0 的点先入队

    vector<int> order;              // 存储拓扑序列
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : adj[u]) {
            if (--indeg[v] == 0) q.push(v);   // 删除 u 后 v 入度归零即可入队
        }
    }
    // 若输出的点数 < n，说明有环（无法拓扑排序）
    if ((int)order.size() != n) cout << "存在环，无拓扑序" << endl;
    else {
        for (int x : order) cout << x << " ";
        cout << endl;
    }
    return 0;
}

// Dijkstra 堆优化模板（必背，CSP-J/NOIP 高频）
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N = 100005;
const long long INF = 1e18;          // 无穷大：用 long long 防溢出
struct Edge { int to, w; };
vector<Edge> adj[N];                 // 邻接表
long long dist[N];                   // 到起点的最短距离
int n, m;

void dijkstra(int s) {
    fill(dist, dist + N, INF);
    dist[s] = 0;                     // 起点到自己是 0
    // 小根堆：按 (距离, 节点) 排序，每次取当前最近的点
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    pq.push(make_pair(0, s));
    while (!pq.empty()) {
        pair<long long, int> top = pq.top(); pq.pop();
        long long d = top.first; int u = top.second;
        if (d != dist[u]) continue;        // 过期元素（已被更短路径更新过）跳过
        for (auto &e : adj[u]) {           // 松弛所有出边
            if (dist[u] + e.w < dist[e.to]) {
                dist[e.to] = dist[u] + e.w;   // 找到更短路就更新
                pq.push(make_pair(dist[e.to], e.to));
            }
        }
    }
}
int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back({v, w});
    }
    dijkstra(1);                       // 求 1 到所有点的最短路
    for (int i = 1; i <= n; i++) cout << dist[i] << " ";
    cout << endl;
    return 0;
}