41 · 图的存储与遍历

① 建图。有向图，m 条弧，g[X].push_back(Y) 一次就够。写成无向会凭空多出一半的边，可达的点变多，输出整片错。

② 排序。题目要“先看编号小的”。DFS 和 BFS 的访问顺序完全由邻接表里的存储顺序决定，不排序得到的是输入顺序决定的序列 —— 样例都过不了。排序总代价 Σ deg(u)·log deg(u) ≤ m log m。

③ 两个序列要分两次遍历，visited 必须重置。一次 DFS 跑完 vis 全是 true，接着跑 BFS 只会输出一个点。这是本题最高频的错误，且不排序、不清零这两件事在样例上都会暴露，所以样例一定要手推一遍。

④ 复杂度。建图 O(m)，排序 O(m log m)，两次遍历各 O(n + m)。m = 10⁶ 时总操作约 2×10⁷ 次，1 秒内。

// 骨架：建图 → 排序 → DFS → 清空 → BFS
for (int i = 0; i < m; ++i) { cin >> x >> y; g[x].push_back(y); }   // 有向，只加一次
for (int u = 1; u <= n; ++u) sort(g[u].begin(), g[u].end());        // 让"最小的邻点"排在最前

dfs(1);  cout << "\n";                     // 先序输出整条 DFS 序列
memset(vis, 0, sizeof(vis));               // ★ 不清零，下一行只会输出一个 1
q.push(1); vis[1] = true;                  // BFS：入队即标记
while (!q.empty()) { /* 出队、输出、把未访问的邻点压进队 */ }

无向图里，能互相到达的点构成一个连通块。数连通块的做法只有一行新代码：外层扫一遍所有点，遇到没访问过的，就说明发现了一个新块，从这里跑一次 DFS 把整块点亮。

int blocks = 0;
for (int i = 1; i <= n; ++i)
    if (!vis[i]) {          // 这个点没被任何已发现的块扫到 → 新块
        ++blocks;
        dfs(i);             // 一次 DFS 把整个块标记完
    }
cout << blocks << "\n";

为什么总复杂度还是 O(n + m)。每次 dfs(i) 只在 vis[i] 为假时启动，而它会把进入的每个点立即标记，所以每个点恰好被进入一次；每个点的邻点表在它自己那次进入时被遍历一次，无向边被两端各看一次，合计 2m 次。外层循环不是乘上去的，因为大多数点会被 continue 掉。

这个外层循环是图论里最常用的一段代码。它其实在回答三个问题：图连不连通（blocks == 1）、有几个独立的部分（blocks 的值）、每个点属于哪个部分（把 ++blocks 换成 block[i] = blocks 在 dfs 里赋值）。有向图里对应的概念叫强连通分量，本节不展开。

再顺手记一个数：若图有 n 个点、m 条边、k 个连通块，则 k ≥ n − m。因为每个连通块至少要有一棵生成树，树边共 n − k 条，而 m 不小于树边数。这个不等式能用来粗查“边数是不是少得可疑”。

二分图：能把点集分成两类，使每条边的两个端点分属不同类。等价说法是图中没有奇环（长度为奇数的环）。判定只要给每个点染一种颜色，要求一条边的两端颜色不同。

染色规则只有一句：color[v] = 3 - color[u]（颜色取 1 和 2）。若某个邻点已经染过、且颜色与 u 相同，就出现了同色边，说明有奇环，直接返回 false。

int color[N];                     // 0 = 未染色, 1 / 2 = 两种颜色

bool isBipartite() {
    for (int s = 1; s <= n; ++s) {            // ★ 每个连通块都要单独起一次
        if (color[s]) continue;
        color[s] = 1;                          // 块内第一个点随便染
        queue<int> q; q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : g[u]) {
                if (!color[v]) {               // 没染过：强制染成反色
                    color[v] = 3 - color[u];
                    q.push(v);
                } else if (color[v] == color[u]) {
                    return false;              // 同色相邻 → 奇环 → 不是二分图
                }
            }
        }
    }
    return true;
}

为什么这样一定对。一条边两端必须异色，所以一个连通块里只要定下任意一个点的颜色，其余所有点的颜色都被唯一确定（沿路径一路翻色）。两种整体配色只差“把 1 和 2 对调”，对判定没有影响。因此“染色过程中出现同色边”当且仅当存在奇环。

三个必须注意的地方：①必须对每个连通块各起一次 BFS —— 只从 1 号点染，别的块全是 0，永远判成二分图；②这只适用于无向图，有向图的“二分”是另一个概念；③自环 (u, u) 会让 color[v] == color[u] 当场成立，立刻判 false，这正好符合“自环是长度 1 的奇环”。复杂度同样是 O(n + m)。

递归 DFS 的深度等于最长的一条链。本题 n 能到 10⁵，如果数据是一条 10⁵ 长的链，递归深度就是 10⁵，每层几十字节，合计几 MB —— 在栈限制 8 MB 的评测机上会 RE。洛谷的栈空间通常够用，但你必须知道这个风险：数组没越界却 RE，先怀疑递归深度。

解法是把“调用栈”自己用一个 vector 实现。顺序能完全一致，关键在逆序压栈：把 u 的邻点从大到小压进去，编号最小的那个就落在栈顶，正好等于递归时“先走最小的那条边”。

void dfs_iter(int s) {
    vector<int> st;                        // 自己当栈用：back() 看栈顶，push_back 压栈
    st.push_back(s);
    while (!st.empty()) {
        int u = st.back();
        st.pop_back();
        if (vis[u]) continue;              // 同一个点可能被多个前驱压进来
        vis[u] = true;
        cout << u << " ";                  // 出栈即输出，位置等价于递归里的"刚进函数"
        // 逆序压栈：让编号最小的邻点留在栈顶
        for (int i = (int)g[u].size() - 1; i >= 0; --i)
            if (!vis[g[u][i]]) st.push_back(g[u][i]);
    }
}

代价是栈里最多压 m 条记录（一个点可能被多个前驱重复压栈），m = 10⁶ 时 4 MB，可以接受。顺便记住这个对应关系：递归 = 系统栈，显式栈 = 自己管；DFS 用栈，BFS 用队列。把 queue 换成 stack，BFS 就变成了“深度优先但顺序不对”的东西，这也说明两种容器的区别不只是写法。