我的图论水平差到了一定地步，整理一些题目。
11th Mar 2026.
最短路
floyd
时间复杂度: \(O(n^3)\)
for (int k = 1; k <= n; ++k)for (int i = 1; i <= n; ++i)for (int j = 1; j <= n; ++j)if (d[i][j] > d[i][k] + d[k][j])d[i][j] = d[i][k] + d[k][j];
dijkstra
时间复杂度: \(O(n^2)\)
inline void djs (int cur) {for (int i = 1; i <= n; ++i) dis[i] = INF;dis[cur] = 0;for (int i = 1; i <= n; ++i) {int k = 0;for (int j = 1; j <= n; ++j) if (!vis[j]) {if (!k) k = j;else if (dis[k] > dis[j] && dis[j] != INF) k = j;}vis[k] = 1;for (auto &j: g[k]) dis[j.y] = std:: min(dis[j.y], dis[k] + j.z);}
}
堆优化的 dijkstra
时间复杂度: \(O((n+m)\log n)\) （所以有时候并不优）
inline void djs (int cur) {std:: priority_queue < NODE > pq;nd.x = cur, nd.z = 0; pq.push(nd);for (int i = 1; i <= n; ++i) dis[i] = INF;dis[cur] = 0;while (!pq.empty()) {nd = pq.top(); pq.pop();int i = nd.x;if (vis[i]) continue;vis[i] = true;for (auto &j: g[i])if (dis[i] + j.z < dis[j.to]) {dis[j.to] = dis[i] + j.z;nd.x = j.to, nd.z = dis[j.to]; pq.push(nd);}}
}
遇到负环：可以同时记录最短路的边数，边数 \(\geq n\) 则存在负环。
联通问题
- 点双连通分量: 删一个点后 其余点仍然联通
- 边双连通分量: 删一个边后 其余点仍然联通
- 割点: 删去此点后不再联通
当且仅当：点 \(u\) 存在儿子 \(v\) 使得 \(low_v \geq dfn_u\) 或点 \(u\) 为搜索的起始点且有 \(\geq 2\) 个儿子时 \(u\) 为割点。 - 割边（桥）: 删去此边后不再联通
当且仅当 \(low_v > dfn_u\) 时边 \((u,v)\) 为割边。
注意：有重边的时候，可以为边加上编号，同时限制无向边不走回头路即可。
以下各题均使用 tarjan 算法，利用时间戳跑 dfs 求解。时间复杂度 \(O(n+m)\)。
P8435 【模板】点双连通分量
int n, m, ans;
std:: vector < int > g[500003], av[500003];
int dfn[500003], low[500003], cnt = 0;
std:: stack < int > s;
void dfs (int x) {dfn[x] = low[x] = ++cnt; s.push(x);for (auto &i: g[x]) if (!dfn[i]) {dfs(i);low[x] = std:: min(low[x], low[i]);if (low[i] >= dfn[x]) {++ans;while (s.size()) {int t = s.top(); s.pop();av[ans].push_back(t);if (t == i) break;}av[ans].push_back(x);}}elselow[x] = std:: min(low[x], dfn[i]);
}inline void kagari () {scanf("%d %d", &n, &m);for (int i = 1; i <= m; ++i) {int x, y; scanf("%d %d", &x, &y);if (x == y) continue;g[x].push_back(y), g[y].push_back(x);}for (int i = 1; i <= n; ++i) if (!dfn[i]) {if (g[i].size()) dfs(i);else av[++ans].push_back(i);}printf("%d\n", ans);for (int i = 1; i <= ans; ++i) {printf("%d ", av[i].size());for (auto &j: av[i]) printf("%d ", j);puts("");} return;
}
P3388 【模板】割点（割顶）
int n, m;
int head[20003], last[200003], to[200003], ccnt = 0;
#define addedge(x, y) last[++ccnt] = head[x], to[ccnt] = y, head[x] = ccnt
int dfn[20003], low[20003], cnt = 0;
bool f[20003]; int ans = 0;inline void dfs (int x, int fa) {dfn[x] = low[x] = ++cnt;int child = 0;#define y to[k]for (int k = head[x]; k; k = last[k]) if (!dfn[y]) {if (y != fa) dfs(y, x), ++child;low[x] = min(low[x], low[y]); if (!fa && child > 1 || fa && low[y] >= dfn[x]) f[x] = true;} else low[x] = min(low[x], dfn[y]);#undef y
}inline void kagari () {scanf("%d %d", &n, &m); for (int i = 1; i <= m; ++i) { int x, y; scanf("%d %d", &x, &y); addedge(x, y), addedge(y, x); }for (int i = 1; i <= n; ++i) if (!dfn[i]) dfs(i, 0);for (int i = 1; i <= n; ++i) if (f[i]) ++ans;printf("%d\n", ans); for (int i = 1; i <= n; ++i) if (f[i]) printf("%d ", i);return;
}
P8436 【模板】边双连通分量
和求桥类似，在 \(dfn_x==low_x\) 时栈顶到 \(x\) 都是一个边连通分量。
int n, m, ans;
std:: vector < std:: pair < int, int > > g[500003];
std:: vector < int > av[500003];
int dfn[500003], low[500003], cnt = 0;
std:: stack < int > s;
void dfs (int x, int last) {dfn[x] = low[x] = ++cnt; s.push(x);for (auto &i: g[x]) {if (i.second == (last ^ 1)) continue; // 不走回头路 if (!dfn[i.first]) {dfs(i.first, i.second);low[x] = std:: min(low[x], low[i.first]);}elselow[x] = std:: min(low[x], dfn[i.first]);}if (dfn[x] == low[x]) {++ans;while (s.size()) {int t = s.top(); s.pop();av[ans].push_back(t);if (t == x) break;}}
}inline void kagari () {scanf("%d %d", &n, &m);for (int i = 1; i <= m; ++i) {int x, y; scanf("%d %d", &x, &y);if (x == y) continue;g[x].push_back(std:: make_pair(y, i << 1)), g[y].push_back(std:: make_pair(x, i << 1 | 1)); // 注意是 2i 和 2i+1 }for (int i = 1; i <= n; ++i) if (!dfn[i]) dfs(i, 0); // 不需要再特判是否是孤立点了，因为在 dfs 时还会加上这个答案 printf("%d\n", ans);for (int i = 1; i <= ans; ++i) {printf("%d ", av[i].size());for (auto &j: av[i]) printf("%d ", j);puts("");} return;
}