[{"type":"Heading1","children":[{"text":"SCC：每一个连通块中任意两点互相可达"}],"slateId":"RgqJU5aWItFgkPbzz_r86"},{"type":"Paragraph","children":[{"text":""}],"slateId":"YUjkG30yhg-eXW6gw1SB0"},{"type":"Heading1","slateId":"X54RwEiU_4q28I5gefo7f","children":[{"text":"不缩点的强连通分量"}]},{"type":"CodeBlock","activeTabIndex":0,"children":[{"type":"CodeTab","language":"plainText","name":"","children":[{"text":"#define int long long\n#define endl '\\n'\n\nconst int N = 1e5 + 5;\n\nint n, m;\n\nvector g[N]; // 原图\n\nint dfn[N]; // 时间戳\nint low[N]; // 能回溯到的最小 dfn\nint scc_id[N]; // 每个点属于哪个 SCC\n\nint stk[N], top; // Tarjan 栈\nbool in_stk[N]; // 是否在栈中\n\nint idx; // 时间戳\nint scc; // SCC 数量\n\nvector scc_nodes[N]; // 每个 SCC 包含的原图点（可选，方便输出）\n\n/*\n Tarjan 求强连通分量\n\n dfn[u] : u 第一次被访问的时间戳\n low[u] : u 能通过 dfs 树边和返祖边回到的最小 dfn\n 当 low[u] == dfn[u] 时，u 是当前 SCC 的根，\n 此时把栈中 u 及以上的点全部弹出来，它们构成一个 SCC。\n*/\nvoid tarjan(int u) {\n low[u] = dfn[u] = ++idx;\n stk[++top] = u;\n in_stk[u] = true;\n\n for (auto v : g[u]) {\n if (!dfn[v]) {\n // v 未被访问：继续 DFS，回溯后用 low[v] 更新 low[u]\n tarjan(v);\n low[u] = min(low[u], low[v]);\n } else if (in_stk[v]) {\n // v 已访问且仍在栈中：说明 (u -> v) 是一条返祖边\n // 用 dfn[v] 更新 low[u]（注意不是 low[v]）\n low[u] = min(low[u], dfn[v]);\n }\n // 若 v 已访问但不在栈中，说明 v 属于别的已完成的 SCC，忽略\n }\n\n // u 是当前 SCC 的根\n if (low[u] == dfn[u]) {\n scc++;\n int v;\n do {\n v = stk[top--];\n in_stk[v] = false;\n\n scc_id[v] = scc; // 记录归属\n scc_nodes[scc].push_back(v); // 记录该 SCC 有哪些点\n } while (v != u);\n }\n}\n\nvoid solve(){\n cin >> n >> m;\n\n for (int i = 1; i <= m; i++) {\n int u, v;\n cin >> u >> v;\n g[u].push_back(v);\n }\n\n // 图不一定连通，需要对每个未访问点都跑一次 Tarjan\n for (int i = 1; i <= n; i++) {\n if (!dfn[i]) {\n tarjan(i);\n }\n }\n\n cout << \"SCC 数量: \" << scc << endl;\n for (int i = 1; i <= scc; i++) {\n cout << \"SCC \" << i << \" : \";\n for (auto x : scc_nodes[i]) cout << x << ' ';\n cout << endl;\n }\n\n // 也可以直接查询任意点 u 属于哪个 SCC：\n // cout << scc_id[u] << endl;\n}\n\nsigned main() {\n ios::sync_with_stdio(false);\n cin.tie(nullptr);\n\n solve();\n\n return 0;\n}"}],"slateId":"cxx4AXQmkLTaf3_qWevH6"}],"slateId":"iotMGDJfesm51Wz9kY0Nj"},{"type":"Paragraph","slateId":"pDFGyYvUrM7x0TeOg9kub","children":[{"text":""}]},{"type":"Heading1","slateId":"zpP03ZNdwyy0lKisrJVzM","children":[{"text":"缩点的强连通分量（拓扑排序）"}]},{"type":"Paragraph","children":[{"text":""},{"type":"Link","title":"https://www.luogu.com.cn/problem/P3387#ide","href":"https://www.luogu.com.cn/problem/P3387#ide","children":[{"text":""}],"slateId":"pLTs1nT4OuUXbGGoxGimW"},{"text":""}],"slateId":"lLBngFluIZC6h0OxQ4M8f"},{"type":"CodeBlock","activeTabIndex":0,"children":[{"type":"CodeTab","language":"plainText","name":"","children":[{"text":"#define int long long\n#define endl '\\n'\ntypedef pair PII;\n\nconst int N = 1e4 + 5;\n\nint n, m;\n\nint a[N]; // 原图每个点的点权\nint sum[N]; // sum[scc]：第 scc 个强连通分量内所有点的点权和\n\nint low[N]; // Tarjan：low[u]\nint dfn[N]; // Tarjan：dfn[u]，时间戳\nint scc_id[N]; // scc_id[u]：原图点 u 属于哪个 SCC\n\nint ind[N]; // 缩点后 DAG 中每个 SCC 的入度\nint stk[N]; // Tarjan 栈\nint f[N]; // f[i]：以缩点后节点 i 结尾的路径最大点权和\n\nint idx; // Tarjan 时间戳\nint top; // 栈顶\nint scc; // SCC 数量\n\nbool in_stk[N]; // 点是否在 Tarjan 栈中\n\nvector g[N]; // 原图\nvector ng[N]; // 缩点后的新图 DAG\nvector scc_nodes[N]; // 每个 SCC 中包含的原图点，本模板中仅用于记录\n\n/*\nTarjan 求强连通分量\n\n参数：\nu：当前遍历到的点\n\n维护：\ndfn[u]：u 第一次被访问的时间戳\nlow[u]：u 能回溯到的最小时间戳\nstk：当前栈\nin_stk[u]：u 是否在栈中\n*/\nvoid tarjan(int u) {\n low[u] = dfn[u] = ++idx; // 初始化时间戳\n stk[++top] = u; // 入栈\n in_stk[u] = true; // 标记在栈中\n\n for (auto v : g[u]) {\n if (!dfn[v]) {\n // v 没访问过，继续 DFS\n tarjan(v);\n low[u] = min(low[u], low[v]);\n } else if (in_stk[v]) {\n // v 已访问且在栈中，说明可以形成强连通关系\n low[u] = min(low[u], dfn[v]);\n }\n }\n\n // 如果 low[u] == dfn[u]，说明 u 是当前 SCC 的根\n if (low[u] == dfn[u]) {\n scc++; // 新强连通分量编号\n\n int v;\n do {\n v = stk[top--]; // 弹栈\n in_stk[v] = false; // 取消栈内标记\n\n scc_id[v] = scc; // 原图点 v 属于第 scc 个 SCC\n scc_nodes[scc].push_back(v); // 记录该 SCC 内有哪些点\n sum[scc] += a[v]; // 累加该 SCC 的点权和\n } while (v != u);\n }\n}\n\nvoid solve() {\n cin >> n >> m;\n\n // 读入点权\n for (int i = 1; i <= n; i++) cin >> a[i];\n\n // 读入原图有向边\n for (int i = 1; i <= m; i++) {\n int u, v;\n cin >> u >> v;\n g[u].push_back(v);\n }\n\n // 对原图跑 Tarjan，求所有强连通分量\n for (int i = 1; i <= n; i++) {\n if (!dfn[i]) {\n tarjan(i);\n }\n }\n\n /*\n 缩点建新图：\n 原图中的每个 SCC 缩成一个点。\n 如果原图中存在边 u -> v，且 scc_id[u] != scc_id[v]，\n 则在缩点后的新图中建边 scc_id[u] -> scc_id[v]。\n 使用 set 去重，避免同一对 SCC 之间重复建边。\n */\n set edgeSet;\n\n for (int u = 1; u <= n; u++) {\n for (auto v : g[u]) {\n int su = scc_id[u];\n int sv = scc_id[v];\n\n // 不同 SCC 之间才需要建缩点边\n if (su != sv && edgeSet.insert({su, sv}).second) {\n ng[su].push_back(sv); // 新图加边\n ind[sv]++; // 新图入度增加\n }\n }\n }\n\n /*\n 缩点后一定是 DAG，因此可以在 DAG 上做拓扑排序 + DP。\n\n f[i] 表示：\n 以缩点后节点 i 作为路径终点时，能获得的最大点权和。\n\n 对于入度为 0 的 SCC，它可以作为路径起点，\n 因此 f[i] 初始化为 sum[i]。\n */\n queue q;\n\n for (int i = 1; i <= scc; i++) {\n if (!ind[i]) {\n q.push(i);\n f[i] = sum[i];\n }\n }\n\n int res = 0; // 最终答案\n\n while (q.size()) {\n auto u = q.front();\n q.pop();\n\n // 更新答案\n res = max(res, f[u]);\n\n // 拓扑转移\n for (auto v : ng[u]) {\n // 从 u 走到 v，则路径权值增加 sum[v]\n f[v] = max(f[v], f[u] + sum[v]);\n\n // 入度减 1，减到 0 就可以入队\n if (!(--ind[v])) {\n q.push(v);\n }\n }\n }\n\n cout << res << endl;\n}"}],"slateId":"d9cMMG9YaMm2smMFDsi2_"}],"slateId":"054K9vEAWvO6zH-FB8gTx"}]

分享｜有向图强连通分量模板(SCC)