缩点(有向图找强连通分量(互通块))
https://www.luogu.com.cn/problem/P3387
1#include <bits/stdc++.h>2using namespace std;3const int N = 1e4 + 10, E = 2e5 + 10;4int n, m;5struct A {6 int first[N], to[E], nxt[E], cnt;7 void adde(int u, int v) {8 ++cnt;9 to[cnt] = v;10 nxt[cnt] = first[u];11 first[u] = cnt;12 }13} o, asd; int w[N];14queue<int> q;15int dfn[N], id, low[N], insta[N], sta[N], top;66 collapsed lines
16int col[N], colcnt, colw[N];17int f[N], in[N];18void dfs(int u) {19 dfn[u] = low[u] = ++id;20 sta[++top] = u; insta[u] = 1;21 for (int p = o.first[u]; p; p = o.nxt[p]) {22 int v = o.to[p];23 if (dfn[v] == 0) {24 dfs(v);25 // v 在搜索树上搜完了26 // low[u] 的定义:搜索树上 u 的子树最多经过一条后向边能到达的时间戳27 low[u] = min(low[u], low[v]);28 }29 else {30 if (insta[v])31 low[u] = min(low[u], dfn[v]);32 // 注意!这里 insta 不是搜索栈,而是未确定强连通块的点的栈33 // 为什么这里是 insta 才更新呢?34 // 如果不 insta[v],注意此时 dfn[v] != 0 说明 v 已经访问过了,然而这说明访问 v 所在强连通块并不包含 u35 // 如果 insta[v],就很抽象了,我也不好说,你自己记住吧36 }37 }38 if (low[u] == dfn[u]) {39 ++colcnt;40 do {41 col[sta[top]] = colcnt;42 colw[colcnt] += w[sta[top]];43 insta[sta[top]] = 0;44 } while (sta[top--] != u);45 }46}47int main() {48 ios::sync_with_stdio(0); cin >> n >> m;49 for (int i = 1; i <= n; ++i) {50 cin >> w[i];51 } for (int i = 1; i<= m; ++i) {52 int u, v; cin >> u >> v; o.adde(u, v);53 }54 for (int i = 1; i <= n; ++i) {55 if (not dfn[i])56 dfs(i);57 }58 for (int u = 1; u <= n; ++u) for (int p = o.first[u]; p; p = o.nxt[p])59 {60 int v = o.to[p];61 if (col[u] != col[v])62 asd.adde(col[u], col[v]), ++in[col[v]];63 }64 int ans = 0;65 for (int i = 1; i <= colcnt; ++i)66 if (in[i] == 0) q.push(i);67 while (not q.empty()) {68 int u = q.front(); q.pop();69 f[u] += colw[u];70 if (f[u] > ans) ans = f[u];71 for (int p = asd.first[u]; p ; p= asd.nxt[p]) {72 int v = asd.to[p];73 if (f[u] > f[v])74 f[v] = f[u];75 --in[v];76 if (in[v] == 0) q.push(v);77 }78 }79 cout << ans << endl;80 return 0;81}