算法竞赛图论题目checklist

通用

• 图是有向图还是无向图？
• 是否有重边/平行边？这可能会影响存图的方式（比如邻接矩阵无脑赋值会导致边权覆盖问题），以及算法的细节逻辑（比如 tarjan 割边）。
• 图是否有自环？是否有环（对于有向图来说）。
• 图是否有边权？是否有负边权？

Dijkstra

• 使用小根堆，重载 <。
• 距离是否初始化成无穷大，无穷大是否够大，有没有必要开 long long？
• 是否还未开始求就标记了源点已经被访问？

Floyd

• 邻接矩阵存图，特别注意有没有重边
• 先枚举松弛点 k，再枚举 i 和 j，才是正确的 DP 逻辑（松弛点是阶段）

Prim

• 不要和最短路写混了，距离维护的是当前点集到其他点的最短距离，是树与点的距离。
• 在某些情况下，可以魔改后按照拓扑序求 DAG 的最小树形图。
• 距离是否初始化成无穷大，无穷大是否够大，有没有必要开 long long？
• 是否还未开始求就标记了源点已经被访问？

Kruskal

• 先排序。
• kruskal 可以求不连通的图的最小生成森林，所以要注意图是否连通。
• 看数据范围，决定是否需要同时路径压缩与按秩合并。

Tarjan

强连通分量

使用 raw_e 存储原图，使用 e 存储缩点后的图。

• 图不一定连通，所以要枚举每个点作为入口，没访问过的就进去跑 tarjan
• tarjan 的过程中，记得遍历的是 raw_e
• 对于已经访问过的点，且在栈内，才可以用来更新 low[u]
• 弹出强连通分量中的结点时，记得把入栈标记信息清掉

缩点

使用 raw_e 存储原图，使用 e 存储缩点后的图。

• 建立新图时，使用新的编号建边
• 两个点同属于不同的 scc，才连边

for (int u = 1; u <= n; u++) {
    // 可能需要写一些点权相关的逻辑
    w[belong[u]] += raw_w[u];
    for (auto v : raw_e[u]) {
        if (belong[u] != belong[v]) {
            e[belong[u]].push_back(belong[v]);
            deg[belong[v]]++;
        }
    }
}

割边

割边是无向图里的概念

• 是否有重边？如果实现时是判断父边的 id 则无视这一条，如果是判断父亲结点则需要调整。