OI笔记 | 基础图论模板
Kruskal 求最小生成树
将边按权值从小到大排序后顺序枚举。如果一条边的 $u$ 和 $v$ 还没有连通，贪心地加上这条边。
判断 $u$ 和 $v$ 是否连通可以用并查集。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 2e5 + 10;
struct edge {
int u, v, w;
bool operator < (const edge &t) const {
return w < t.w;
}
} a[MAX_N];
int f[MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
int find(int x) {
if(f[x] == x) return x;
return (f[x] = find(f[x]));
}
int main() {
int n = read(), m = read(), cnt = 0;
ll ans = 0;
for(int i = 1; i <= n; i++) f[i] = i;
for(int i = 1; i <= m; i++) a[i].u = read(), a[i].v = read(), a[i].w = read();
sort(a + 1, a + m + 1);
for(int i = 1; i <= m; i++) {
int fu = find(a[i].u), fv = find(a[i].v);
if(fu != fv){
ans += a[i].w;
f[fu] = fv;
if((++cnt) == n - 1) break;
}
}
if(cnt == n - 1) write(ans);
else printf("orz");
return 0;
}
例题 苗条的生成树(Slim Span)
求所有生成树中最大边权与最小边权差最小的，输出它们的差值。
题解
紫书上的解法。将边按边权排序，从小到大枚举 $l$，从 $l$ 到 $n$ 枚举 $r$，不断将 $r$ 加入并查集，直到连成一个生成树，枚举下一个 $l$ 并维护答案。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 2e5 + 10, INF = (1 << 30);
struct edge {
int u, v, w;
bool operator < (const edge &t) const {return w < t.w;}
} g[MAX_N];
int f[MAX_N], n, m, cnt;
inline ll read() {...}
inline void write(ll x) {...}
int find(int x) {return f[x] == x ? x : (f[x] = find(f[x]));}
int main() {
while(n = read()) {
m = read();
int ans = INF;
for(int i = 1; i <= m; i++) g[i].u = read(), g[i].v = read(), g[i].w = read();
sort(g + 1, g + m + 1);
for(int i = 1; i <= m; i++) {
cnt = 0;
for(int i = 1; i <= n; i++) f[i] = i;
for(int j = i; j <= m; j++) {
int fu = find(g[j].u), fv = find(g[j].v);
if(fu != fv) {
f[fu] = fv;
if((++cnt) == n - 1) {
ans = min(ans, g[j].w - g[i].w);
break;
}
}
}
}
write(ans == INF ? -1 : ans); putchar('\n');
}
return 0;
}
dijkstra
给定一个 $n$ 个点，$m$ 条有向边的带非负权图，请你计算从 $s$ 出发，到每个点的距离。
数据保证你能从 $s$ 出发到任意点。
题解
dijkstra 的过程如下：
-
初始化
d[s]=0，其它d[i]=INF。清除vis数组。 -
选出
d最小的节点u（vis[u]==0）。 -
遍历
u的所有出边(u,v,w)，更新d[v]=min(d[v],d[u]+w)。 -
如果没有完成，回到第 2 步。
用堆来优化第 2 步的复杂度。时间复杂度：$O((n+m)\log n)$。
参考代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX_N = 1e5 + 10, INF = (1ll << 31) - 1;
struct Edge {int u, v, w;};
vector<Edge> edges;
vector<int> G[MAX_N];
int d[MAX_N], n, m, s;
bool vis[MAX_N];
inline void AddEdge(int u, int v, int w) {
edges.push_back({u, v, w});
G[u].push_back(edges.size() - 1); // 存的是边的标号
}
inline void dijkstra() {
priority_queue<pii, vector<pii>, greater<pii>> q;
for(int i = 1; i <= n; i++) d[i] = INF;
d[s] = 0;
q.push({0, s});
while(!q.empty()) {
int u = q.top().second; q.pop();
if(vis[u]) continue;
vis[u] = true;
for(int i = 0; i < G[u].size(); i++) {
int v = edges[G[u][i]].v, w = edges[G[u][i]].w;
if(d[u] + w < d[v]) {
d[v] = d[u] + w;
q.push({d[v], v});
}
}
}
}
inline ll read() {...}
inline void write(ll x) {...}
int main() {
n = read(), m = read(), s = read();
for(int i = 1; i <= m; i++) {
int u = read(), v = read(), w = read();
AddEdge(u, v, w);
}
dijkstra();
for(int i = 1; i <= n; i++) write(d[i]), putchar(' ');
return 0;
}
例题 邮递员送信
有一个邮递员要送东西，邮局在节点 $1$。他总共要送 $n-1$ 样东西，其目的地分别是节点 $2$ 到节点 $n$。由于这个城市的交通比较繁忙，因此所有的道路都是单行的，共有 $m$ 条道路。这个邮递员每次只能带一样东西，并且运送每件物品过后必须返回邮局。求送完这 $n-1$ 样东西并且最终回到邮局最少需要的时间。
题解
我们对原图跑一遍 dijkstra，再对反图跑一遍 dijkstra。这是一个比较重要的技巧：对多到一的最短路，考虑进行“反向建边”。
对于反图的存储，我们可以在原图的编号上加上 $n$，直接存在原图上。
参考代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX_N = 2e3 + 10, INF = (1ll << 31) - 1;
struct Edge {int u, v, w;};
vector<Edge> edges;
vector<int> G[MAX_N];
int d[MAX_N], n, m;
bool vis[MAX_N];
inline void AddEdge(int u, int v, int w){edges.push_back({u, v, w}); G[u].push_back(edges.size() - 1);}
inline void dijkstra(int s) {
priority_queue<pii, vector<pii>, greater<pii>> q;
for(int i = 1; i <= 2 * n; i++) d[i] = INF;
d[s] = 0; q.push({0, s});
while(!q.empty()) {
int u = q.top().second; q.pop();
if(vis[u]) continue;
vis[u] = true;
for(int i = 0; i < G[u].size(); i++) {
int v = edges[G[u][i]].v, w = edges[G[u][i]].w;
if(d[u] + w < d[v]) {
d[v] = d[u] + w;
q.push({d[v], v});
}
}
}
}
inline ll read() {...}
inline void write(ll x) {...}
int main() {
ll ans = 0;
n = read(), m = read();
for(int i = 1; i <= m; i++) {
int u = read(), v = read(), w = read();
AddEdge(u, v, w);
AddEdge(v + n, u + n, w);
}
dijkstra(1);
for(int i = 2; i <= n; i++) ans += d[i];
dijkstra(n + 1);
for(int i = n + 2; i <= n * 2; i++) ans += d[i];
write(ans);
return 0;
}
Spfa 求负环
显然任何一个路径长 $cnt$ 不小于 $n$ 即存在负环。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 2e3 + 10, INF = 1e9 + 7;
struct edge {int u, v, w;};
vector<edge> edges;
vector<int> G[MAX_N];
int dis[MAX_N], cnt[MAX_N], n, m;
bool vis[MAX_N];
inline void AddEdge(int u, int v, int w) {
edges.push_back({u, v, w});
G[u].push_back(edges.size() - 1);
}
inline ll read() {...}
inline void write(ll x) {...}
inline bool spfa(int s) {
for(int i = 1; i <= n; i++) dis[i] = INF, vis[i] = 0, cnt[i] = 0;
queue<int> q; q.push(s);
dis[s] = 0, vis[s] = 1;
while(!q.empty()) {
int u = q.front(); q.pop();
vis[u] = 0;
for(int i = 0; i < G[u].size(); i++) {
int v = edges[G[u][i]].v, w = edges[G[u][i]].w;
if(dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
cnt[v] = cnt[u] + 1;
if(cnt[v] >= n) return 0;
if(!vis[v]) q.push(v), vis[v] = 1;
}
}
}
return 1;
}
int main() {
int T = read();
while(T--) {
edges.clear();
for(int i = 1; i <= n; i++) G[i].clear();
n = read(), m = read();
for(int i = 1; i <= m; i++) {
int u = read(), v = read(), w = read();
AddEdge(u, v, w);
if(w >= 0) AddEdge(v, u, w);
}
puts(spfa(1) ? "NO" : "YES");
}
return 0;
}
差分约束系统
给出一组包含 $m$ 个不等式，有 $n$ 个未知数的形如：
\[\begin{cases} x_{c_1}-x_{c'_1}\leq y_1 \\x_{c_2}-x_{c'_2} \leq y_2 \\ \cdots\\ x_{c_m} - x_{c'_m}\leq y_m\end{cases}\]的不等式组，求任意一组满足这个不等式组的解。
关于这种题，移项一下，得到 $x_{c_1}\leq y_1 + x_{c’1}$，类比图上最短路的三角不等式 $dis{v}\le w_{u\to v} + dis_{u}$，我们可以连一条边权为 $y$ 的有向边 $c’_1 \to c_1$，然后创建一个源点 $0$ 号节点，把它连向所有节点。那么跑一遍最短路，$dis_i$ 即为 $x_i$。
用 spfa 来跑是因为可以找负环，而一旦有负环存在，不等式就无解。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 5e3 + 10, INF = (1 << 30);
struct edge{int u, v, w;};
vector<edge> edges;
vector<int> G[MAX_N];
int n, m;
bool vis[MAX_N];
int dis[MAX_N], cnt[MAX_N];
void AddEdge(int u, int v, int w) {
edges.push_back((edge){u, v, w});
G[u].push_back(edges.size() - 1);
}
inline ll read() {...}
inline void write(ll x) {...}
bool spfa(int s) {
queue<int> q;
q.push(s);
for(int i = 1; i <= n; i++)
dis[i] = INF;
while(!q.empty()) {
int u = q.front(); q.pop();
vis[u] = 0;
for(int i = 0; i < (int)G[u].size(); i++) {
int v = edges[G[u][i]].v, w = edges[G[u][i]].w;
if(dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
cnt[v] = cnt[u] + 1;
if(cnt[v] >= n + 1) return 0;
if(!vis[v]) q.push(v), vis[v] = 1;
}
}
}
return 1;
}
int main() {
n = read(), m = read();
for(int i = 1; i <= n; i++)
AddEdge(0, i, 0);
for(int i = 1; i <= m; i++) {
int x = read(), y = read(), d = read();
AddEdge(y, x, d);
}
if(spfa(0))
for(int i = 1; i <= n; i++)
write(dis[i]), putchar(' ');
else puts("NO");
return 0;
}
Johnson 全源最短路
给定一个包含 $n$ 个结点和 $m$ 条带权边（可负）的有向图，求所有点对间的最短路径长度，一条路径的长度定义为这条路径上所有边的权值和。
若图中存在负环，输出仅一行 $-1$。
若图中不存在负环：
令 $dis_{i,j}$ 为从 $i$ 到 $j$ 的最短路，在第 $i$ 行输出 $\sum\limits_{j=1}^n j\times dis_{i,j}$。
如果不存在从 $i$ 到 $j$ 的路径，则设 $dis_{i,j}=10^9$。
题解
详细证明见 oi-wiki。
简单来说我们建一个虚拟节点 $0$，从它出发连上其他所有节点（边权为 $0$）。从 $0$ 节点出发跑一遍 SPFA，用于计算出每个节点到它的距离 $h_i$。然后我们把每条边的边权 $w$ 变成 $w+h_u-h_v$ 从而让所有边权为正，接下来就可以对每个点跑一轮堆优化的 dijkstra 了。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const int MAX_N = 3e3 + 10, INF = 1e9;
struct Edge {
int u, v;
ll w;
};
vector<Edge> edges;
vector<int> G[MAX_N];
int cnt[MAX_N], n, m;
ll h[MAX_N], d[MAX_N];
bool vis[MAX_N];
inline void AddEdge(int u, int v, int w) {
edges.push_back({u, v, w});
G[u].push_back(edges.size() - 1);
}
inline ll read() {...}
inline void write(ll x) {...}
bool spfa(int s) {
queue<int> p;
memset(h, 63, sizeof(h));
h[s] = 0, vis[s] = 1;
p.push(s);
while(!p.empty()) {
int u = p.front(); p.pop();
vis[u] = 0;
for(int i = 0; i < G[u].size(); i++) {
Edge e = edges[G[u][i]];
if(h[e.v] > h[u] + e.w) {
h[e.v] = h[u] + e.w;
if(!vis[e.v]) {
vis[e.v] = 1;
p.push(e.v);
if(++cnt[e.v] > n) return false;
}
}
}
}
return true;
}
void dijkstra(int s) {
priority_queue<pll, vector<pll>, greater<pll>> q;
memset(vis, 0, sizeof(vis));
for(int i = 1; i <= n; i++) d[i] = INF;
d[s] = 0; q.push({0, s});
while(!q.empty()) {
int u = q.top().second; q.pop();
if(vis[u]) continue;
vis[u] = 1;
for(int i = 0; i < G[u].size(); i++) {
Edge e = edges[G[u][i]];
if(d[e.v] > d[u] + e.w) {
d[e.v] = d[u] + e.w;
q.push({d[e.v], e.v});
}
}
}
}
int main() {
n = read(), m = read();
for(int i = 1; i <= m; i++) {
int u = read(), v = read(), w = read();
AddEdge(u, v, w);
}
for(int i = 1; i <= n; i++) AddEdge(0, i, 0);
if(!spfa(0)) {write(-1); return 0;}
for(int i = 0; i < m; i++) edges[i].w += h[edges[i].u] - h[edges[i].v];
for(int i = 1; i <= n; i++) {
dijkstra(i);
ll ans = 0;
for(int j = 1; j <= n; j++) {
if(d[j] == INF) ans += 1ll * INF * j;
else ans += 1ll * (d[j] + h[j] - h[i]) * j;
};
write(ans); putchar('\n');
}
return 0;
}
拓扑排序
一个不同的值的升序排序数列指的是一个从左到右元素依次增大的序列，例如，一个有序的数列 $A,B,C,D$ 表示$A<B,B<C,C<D$。在这道题中，我们将给你一系列形如 $A<B$ 的关系，并要求你判断是否能够根据这些关系确定这个数列的顺序。
若根据前 $x$ 个关系即可确定这 $n$ 个元素的顺序 yyy..y（如 ABC），输出
Sorted sequence determined after xxx relations: yyy...y.
若根据前 $x$ 个关系即发现存在矛盾（如 $A<B,B<C,C<A$），输出
Inconsistency found after x relations.
若根据这 $m$ 个关系无法确定这 $n$ 个元素的顺序，输出
Sorted sequence cannot be determined.
题解
考虑若 $A<B$，则连一条有向边 $A\to B$。如果能成功使用 Kahn 算法进行拓扑排序，那么序列的顺序就确定了。
Kahn 算法的伪代码如下：
L ← 存储拓扑排序后的节点顺序
S ← 入度为零的节点队列
若 S 非空
从 S 的前端取出 u 并弹出
将 u 插入 L
枚举 u 为入边的所有边 (u,v)
删除 (u,v)
如果 v 入度为 0
将 v 插入 S
如果图还有边
拓扑排序失败
否则
返回 L
对应到这一题，我们每建一条边就要进行拓扑排序，同时判断：
-
如果答案数组的长度小于 $n$，就有环（矛盾）。这是因为如果有点还孤立，它的入度也为 $0$，同样会被我们
bfs到。只有在有环的情况下，才会有点没被bfs。 -
如果还有点孤立，顺序就还没有确定，拓扑排序的结果不能作为答案。
参考代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 30;
bool g[MAX_N][MAX_N], vis[MAX_N];
int in[MAX_N], inn[MAX_N], n, m, cnt, tt;
vector<int> ans;
queue<int> s;
inline ll read() {...}
inline void write(ll x) {...}
bool topo() {
vector<int> t;
for(int i = 1; i <= n; i++) {
inn[i] = in[i]; // 每一次排序都要删边，不能在原图上操作
if(inn[i] == 0) s.push(i);
}
while(!s.empty()) {
int u = s.front();
s.pop();
t.push_back(u);
for(int v = 1; v <= n; v++) {
if(!g[u][v]) continue;
if(--inn[v] == 0) s.push(v);
}
}
if(t.size() < n) return 0; // 有环的情况
ans = t;
return 1;
}
int main() {
n = read(), m = read();
string tmp;
for(int i = 1; i <= m; i++) {
cin >> tmp;
int u = tmp[0] - 'A' + 1, v = tmp[2] - 'A' + 1;
if(!vis[u]) tt++, vis[u] = 1;
if(!vis[v]) tt++, vis[v] = 1; // tt 表示已经连入图的点数
if(!g[u][v]) in[v]++;
g[u][v] = 1;
int res = topo();
if(!res) {
printf("Inconsistency found after %d relations.", i);
return 0;
}
else if(res == 1 && !cnt && tt == n) cnt = i;
// 所有点都被连入图了且拓扑排序成功，那么记录答案位置
}
if(cnt) {
printf("Sorted sequence determined after %d relations: ", cnt);
for(int i = 0; i < ans.size(); i++) putchar(ans[i] - 1 + 'A');
putchar('.');
}
else printf("Sorted sequence cannot be determined.");
return 0;
}
并查集
模板
给出A地区的村庄数 $N$，和公路数 $M$，公路是双向的。并告诉你每条公路的连着哪两个村庄，并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在至少一条修复完成的道路（可以由多条公路连成一条道路）
题解
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1005;
int f[MAX_N];
struct road {
int u, v, t;
bool operator < (const road &w) const {
return t < w.t;
}
};
vector <road> roads;
inline ll read() {...}
void write(ll x) {...}
int find(int k) {
if(f[k] == k) return k;
return f[k] = find(f[k]);
}
int main() {
int n = read(), m = read(), ans = -1;
for(int i = 1; i <= n; i++) f[i] = i;
for(int i = 1; i <= m; i++) {
road tmp;
tmp.u = read(), tmp.v = read(), tmp.t = read();
roads.push_back(tmp);
}
sort(roads.begin(), roads.end());
for(int i = 0; i < roads.size(); i++) {
int fu = find(roads[i].u);
int fv = find(roads[i].v);
if(fu != fv) f[fu] = fv, n--;
if(n == 1) {
ans = roads[i].t;
break;
}
}
write(ans);
return 0;
}
利用并查集求最小环
有 $n$ 个同学（编号为 $1$ 到 $n$ ）正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象，其中，编号为 $i$ 的同学的信息传递对象是编号为 $T_i$ 的同学。
游戏开始时，每人都只知道自己的生日。之后每一轮中，所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象（注意：可能有人可以从若干人那里获取信息， 但是每人只会把信息告诉一个人，即自己的信息传递对象）。当有人从别人口中得知自己的生日时，游戏结束。请问该游戏一共可以进行几轮？
题解
从 $u$ 到 $v$ 信息传递的过程可以视为从 $u$ 到 $v$ 连一条边。建完图后考虑图上最小环的长度即为答案。
可以使用并查集来查询是否形成环、计算环的长度。需要在原始的并查集基础上同时更新距离。也就是在树上往上走时使得 $dis_x$ 加上 $dis_{fa_x}$。注意这一步距离在路径压缩后再加，这样原来的 $dis_{fa_x}$ 会先被更新。环的长度即为 $dis_v+1$。
时间复杂度：$O(n)$。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 2e5 + 10;
int f[MAX_N], dis[MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
int fa(int x) {
if(f[x] == x) return x;
int fo = f[x];
f[x] = fa(f[x]);
dis[x] += dis[fo];
return f[x];
}
int main() {
int n = read(), ans = (1 << 30);
for(int i = 1; i <= n; i++) f[i] = i;
for(int u = 1; u <= n; u++) {
int v = read();
int fu = fa(u), fv = fa(v);
if(fu == fv) ans = min(ans, dis[v] + 1);
else f[fu] = fv, dis[u] = dis[v] + 1;
}
write(ans);
return 0;
}
倍增LCA
给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。
题解
倍增算法是最经典的 LCA 求法，也可以用欧拉序列转化为 RMQ 问题，但我不会。
首先预处理出以 $2$ 为底的所有对数。
求 LCA 之前，还需要先 dfs 一遍，处理出每个点的深度和它的第 $2^i$ 个祖先，方便之后倍增地跳。用 $fa_{p,i}$ 存储节点 $p$ 的第 $2^i$ 个祖先 ，那么容易知道 $fa_{p,i}=fa_{fa_{p,i-1},i-1}$。
求 LCA 时，先跳到同一高度，然后一起往上倍增地跳，直到他们的父亲相同。
void dfs(int u, int pre) {
fa[u][0] = pre;
dep[u] = dep[pre] + 1;
for(int i = 1; i < MAX_LOG; i++)
fa[u][i] = fa[fa[u][i - 1]][i - 1];
for(int v : G[u])
if(v != pre) dfs(v, u);
}
int lca(int x, int y) {
if(dep[x] < dep[y]) swap(x, y);
for(int i = MAX_LOG - 1; i >= 0; i--)
if(fa[x][i] && dep[fa[x][i]] >= dep[y]) x = fa[x][i];
if(x == y) return x;
for(int i = MAX_LOG - 1; i >= 0; i--)
if(fa[x][i] && fa[y][i] && fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
return fa[x][0];
}
Tarjan(缩点)
给定一个 $n$ 个点 $m$ 条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。
允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。
$1\le n \le 10^4$，$1\le m \le 10^5$，$0\le a_i\le 10^3$。
题解
第一次写 Tarjan，有点难调。。
给出的是有向图，其中可能有环。（根据题目的名字） 我们要把图上的所有 强连通分量(SCC) 缩成一个点，从而让这个图变成 DAG，从而可以进行 topo 排序，做 DAG 上的 dp。
不妨用 Tarjan 算法求 SCC，从而缩点建一个新图。
参考代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e4 + 10;
struct edge {int u, v;};
vector<edge> edges;
int n, m, p[MAX_N], dfn[MAX_N], low[MAX_N], belong[MAX_N], dp[MAX_N], st[MAX_N], in[MAX_N], stsiz, dfncnt;
vector<int> G[MAX_N], DAG[MAX_N];
bool vis[MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
void AddEdge(int u, int v) {
edges.push_back({u, v});
G[u].push_back(edges.size() - 1);
}
void tarjan(int u) {
low[u] = dfn[u] = ++dfncnt, st[++stsiz] = u, vis[u] = true;
for(int i = 0; i < G[u].size(); i++) {
int v = edges[G[u][i]].v;
if(!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
else if(vis[v]) low[u] = min(low[u], dfn[v]);
}
if(dfn[u] == low[u]) {
// 若 dfn[n] == low[u] ，栈 st 中 u 以上的点构成一个 SCC
int tp;
while(tp = st[stsiz--]) {
belong[tp] = u; // SCC 中其他点的 belong 都是 u ，只有 u 的 belong 是它自己
vis[tp] = false;
if(tp == u) break;
p[u] += p[tp]; // 把 SCC 中的其他点权加到 u 中
}
}
}
int topo() {
queue<int> q;
for(int i = 1; i <= n; i++) {
if(belong[i] == i && in[i] == 0) {
// 我们不考虑 SCC 中的其他点，所以要求 belong[i] == i
q.push(i);
dp[i] = p[i];
}
}
while(!q.empty()) {
int u = q.front(); q.pop();
for(int i = 0; i < DAG[u].size(); i++) {
int v = DAG[u][i];
dp[v] = max(dp[v], dp[u] + p[v]);
if(--in[v] == 0) q.push(v);
}
}
int ret = 0;
for(int i = 1; i <= n; i++) ret = max(ret, dp[i]);
return ret;
}
int main() {
n = read(), m = read();
for(int i = 1; i <= n; i++) p[i] = read();
for(int i = 1; i <= m; i++) {
int u = read(), v = read();
AddEdge(u, v);
}
for(int i = 1; i <= n; i++) if(!dfn[i]) tarjan(i);
for(int i = 0; i < edges.size(); i++) {
int u = belong[edges[i].u], v = belong[edges[i].v];
// 如果两个点不在同一个强连通分量里，把他们的 belong 连边
if(u != v) {
DAG[u].push_back(v);
in[v]++;
}
}
write(topo());
return 0;
}
例题 受欢迎的牛
每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果 $A$ 喜欢 $B$，$B$ 喜欢 $C$，那么 $A$ 也喜欢 $C$。牛栏里共有 $N$ 头奶牛，给定一些奶牛之间的爱慕关系，请你算出有多少头奶牛可以当明星。
题解
用 Tarjan 求强连通分量，其中某个强连通分量如果出度为 $0$，那么它里面的所有奶牛都会是明星奶牛。
特别地，如果有多个强连通分量出度为 $0$，那谁也做不了明星奶牛。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e4 + 10;
struct edge {int u, v;};
vector<edge> edges;
vector<int> G[MAX_N];
int dfn[MAX_N], low[MAX_N], out[MAX_N], scc[MAX_N], sz[MAX_N], st[MAX_N], stsiz, sccsiz, dfncnt;
bool vis[MAX_N];
inline ll read() {
ll ret = 0, w = 1; char c = getchar();
while(!isdigit(c)) {if(c == '-') w = -1; c = getchar();}
while(isdigit(c)) {ret = (ret << 1) + (ret << 3) + (c ^ 48); c = getchar();}
return ret * w;
}
inline void write(ll x) {
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + 48);
}
inline void AddEdge(int u, int v) {
edges.push_back({u, v});
G[u].push_back(edges.size() - 1);
}
void tarjan(int u) {
dfn[u] = low[u] = ++dfncnt, st[++stsiz] = u, vis[u] = 1;
for(int i = 0; i < G[u].size(); i++) {
int v = edges[G[u][i]].v;
if(!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
else if(vis[v]) low[u] = min(low[u], dfn[v]);
}
if(low[u] == dfn[u]) {
int tp;
sccsiz++;
while(tp = st[stsiz--]) {
scc[tp] = sccsiz;
sz[sccsiz]++;
vis[tp] = 0;
if(tp == u) break;
}
}
}
int main() {
int n = read(), m = read();
for(int i = 1; i <= m; i++) {
int u = read(), v = read();
AddEdge(u, v);
}
for(int i = 1; i <= n; i++) if(!dfn[i]) tarjan(i);
for(int i = 0; i < edges.size(); i++) {
int u = edges[i].u, v = edges[i].v;
if(scc[u] != scc[v]) out[scc[u]]++;
}
int f = 0, ans = 0;
for(int i = 1; i <= sccsiz; i++) if(!out[i]) ans = sz[i], f++;
if(f == 1) write(ans);
else write(0);
return 0;
}
树链剖分
重链剖分，见 LINK。
♥