const int MAXN 210; // n ≤ 100两倍空间 vectorint g[MAXN]; int dfn[MAXN], low[MAXN], scc_id[MAXN]; int stk[MAXN], top, ts, scc_cnt; bool ins[MAXN]; void tarjan(int u) { dfn[u] low[u] ts; stk[top] u; ins[u] true; for (int v : g[u]) { if (!dfn[v]) { tarjan(v); low[u] min(low[u], low[v]); } else if (ins[v]) { low[u] min(low[u], dfn[v]); } } if (low[u] dfn[u]) { scc_cnt; int x; do { x stk[top--]; ins[x] false; scc_id[x] scc_cnt; } while (x ! u); } }一、Tarjan 是用来求什么的核心用途求有向图的「强连通分量」Strongly Connected Component, SCC1. 什么是强连通分量在有向图中如果从点u能走到v且从v也能走回u就说u和v强连通。强连通分量就是一个极大的子图里面任意两点都强连通。举个例子1 → 2 ↘ ↑ ↓ 3 ↖---4 ↙在这个图中{1,2,4}是一个 SCC因为它们可以互相到达。2. Tarjan 的典型应用场景2-SAT 判定缩点建 DAG如“受欢迎的牛”、“间谍网络”判断一个点是否在环中求解双连通分量边双 / 点双是 Tarjan 的变种编译器优化、依赖分析二、Tarjan 的核心思想DFS 时间戳Tarjan 的本质是在一次 DFS 过程中动态维护每个点能“回溯”到的最早祖先。1. 几个关键数组灵魂所在数组含义dfn[u]DFS 序点u第一次被访问的时间戳low[u]u通过树边 最多一条返祖边能到达的最早dfnstack当前 DFS 路径上的结点栈in_stack[u]结点是否在栈中一句话理解 lowlow[u]表示从u出发沿着 DFS 树往下走再绕回来最早能回到哪个祖先。2. Tarjan 的执行流程重点从根开始 DFS访问点u记录dfn[u] low[u] timestamp把u压入栈标记在栈中遍历u的所有出边(u → v)情况一v没访问过递归 DFSv回溯时用low[v]更新low[u]low[u] min(low[u], low[v]);情况二v已访问且在栈中返祖边说明v是u的祖先用dfn[v]更新low[u]low[u] min(low[u], dfn[v]);关键点什么时候形成一个 SCC当dfn[u] low[u]时说明u是当前 SCC 的根从栈中弹出u及之上的所有点它们属于同一个 SCC3. 为什么要这样设计直觉解释你可以把 DFS 想象成探险队dfn每个人报到的编号stack当前探险队走过的路径low当前队员能“喊话”到的最早队友当你发现“我u最早只能喊到自己dfn[u] low[u]”那就意味着从我能到达的所有人都无法逃出我这个环这个圈子就是一个强连通分量。三、2-SAT在 2-SAT 中我们建了一个有向图如果x能推出¬x且¬x也能推出x那么x和¬x就在同一个 SCCTarjan 正好能帮我们快速找出所有 SCC判断是否存在x和¬x同 SCC 的矛盾情况这就是为什么 2-SAT 几乎必配 Tarjan。四、时间复杂度O(n m)每个点、每条边只访问一次是目前求 SCC 最快的算法之一另一个是 Kosaraju五、带详细注释的代码void tarjan(int u) { // 1. 给当前点 u 打上时间戳DFS 访问次序 // dfn[u]: u 第一次被访问的顺序编号 // low[u]: u 能追溯到的最早祖先的 dfn 值 dfn[u] low[u] ts; // 2. 将 u 入栈并标记它在栈中 stk[top] u; ins[u] true; // 3. 遍历 u 的所有出边 for (int v : g[u]) { // 情况一v 还没被访问过树边 if (!dfn[v]) { tarjan(v); // 递归访问 v low[u] min(low[u], low[v]); // 用 v 的 low 更新 u 的 low } // 情况二v 已被访问且还在栈中返祖边 else if (ins[v]) { // 说明 v 是 u 的祖先 // 用 v 的 dfn 更新 u 的 low low[u] min(low[u], dfn[v]); } } // 4. 如果 u 是某个 SCC 的根自己就是最早祖先 if (low[u] dfn[u]) { scc_cnt; // 强连通分量个数 1 int x; do { x stk[top--]; // 出栈 ins[x] false; // 取消在栈标记 scc_id[x] scc_cnt; // 给 x 分配 SCC 编号 } while (x ! u); // 一直弹到 u } }如果图是不连通的tarjan只能遍历从首点开始能连通部分找scc需要进行一次循环确保分离多块图的全部scc被找到复杂度已经找到scc的点再次遍历也不会再进行查找dfn是全局数组复杂度依然O(n m)for (int i 1; i n; i) { if (!dfn[i]) tarjan(i); }这段代码“能干出来什么”1. 最重要的输出scc_id[]scc_id[x] 第几号强连通分量所有在同一个 SCC 里的点scc_id相同不同 SCC 的点scc_id不同if (scc_id[i] scc_id[i n]) { // 在一个连通分量里 }2. 强连通分量的总个数scc_cntscc_cnt 图中强连通分量的总数如果scc_cnt n说明图里没有任何环每个点自成一个 SCC如果scc_cnt 1说明整个图是一个大环3. 隐式输出缩点后的 DAG 结构虽然代码里没有直接建新图但可以用scc_id[]自己建 DAGfor (int u 1; u n; u) { for (int v : g[u]) { if (scc_id[u] ! scc_id[v]) { // u 所在的 SCC → v 所在的 SCC } } }2-sat例题https://vjudge.net/problem/%E6%B4%9B%E8%B0%B7-P4171/originDescription满汉全席是中国最丰盛的宴客菜肴有许多种不同的材料透过满族或是汉族的料理方式呈现在数量繁多的菜色之中。由于菜色众多而繁杂只有极少数博学多闻技艺高超的厨师能够做出满汉全席而能够烹饪出经过专家认证的满汉全席也是中国厨师最大的荣誉之一。世界满汉全席协会是由能够料理满汉全席的专家厨师们所组成而他们之间还细分为许多不同等级的厨师。为了招收新进的厨师进入世界满汉全席协会将于近日举办满汉全席大赛协会派遣许多会员当作评审员为的就是要在参赛的厨师之中找到满汉界的明日之星。大会的规则如下每位参赛的选手可以得到 nn 种材料选手可以自由选择用满式或是汉式料理将材料做成菜肴。大会的评审制度是共有 mm 位评审员分别把关。每一位评审员对于满汉全席有各自独特的见解但基本见解是要有两样菜色作为满汉全席的标志。如某评审认为如果没有汉式东坡肉跟满式的涮羊肉锅就不能算是满汉全席。但避免过于有主见的审核大会规定一个评审员除非是在认为必备的两样菜色都没有做出来的状况下才能淘汰一位选手否则不能淘汰一位选手。换句话说只要参赛者能在这两种材料的做法中其中一个符合评审的喜好即可通过该评审的审查。如材料有猪肉羊肉和牛肉时有四位评审员的喜好如下表评审一 评审二 评审三 评审四 满式牛肉 满式猪肉 汉式牛肉 汉式牛肉 汉式猪肉 满式羊肉 汉式猪肉 满式羊肉如参赛者甲做出满式猪肉满式羊肉和满式牛肉料理他将无法满足评审三的要求无法通过评审。而参赛者乙做出汉式猪肉满式羊肉和满式牛肉料理就可以满足所有评审的要求。但大会后来发现在这样的制度下如果材料选择跟派出的评审员没有特别安排好的话所有的参赛者最多只能通过部分评审员的审查而不是全部所以可能会发生没有人通过考核的情形。如有四个评审员喜好如下表时则不论参赛者采取什么样的做法都不可能通过所有评审的考核评审一 评审二 评审三 评审四 满式羊肉 满式猪肉 汉式羊肉 汉式羊肉 汉式猪肉 满式羊肉 汉式猪肉 满式猪肉所以大会希望有人能写一个程序来判断所选出的 mm 位评审会不会发生没有人能通过考核的窘境以便协会组织合适的评审团。Input第一行包含一个数字 KK1≤K≤501≤K≤50代表测试文件包含了 KK 组数据。每一组测试数据的第一行包含两个数字 nn 跟 mmn≤100n≤100m≤1000m≤1000代表有 nn 种材料mm 位评审员。为方便起见舍弃做法的中文名称而给予编号编号分别从 11 到 nn。接下来的 mm 行每行都代表对应的评审员所拥有的两个喜好每个喜好由一个英文字母跟一个数字代表如 m1m1 代表这个评审喜欢第 11 个材料透过满式料理做出来的菜而 h2h2 代表这个评审员喜欢第 22 个材料透过汉式料理做出来的菜。Output每组测试数据输出一行如果不会发生没有人能通过考核的窘境输出GOOD否则输出BAD均为大写字母。一、问题建模1. 变量定义对每一种材料i有两种做法满式记作x_i true汉式记作x_i false于是我们有n个布尔变量x₁ ~ xₙ。2. 评审条件如何转化每个评审给出两个喜好只要满足其中一个就行。例如m3→ 第 3 个材料做满式 →x₃ trueh1→ 第 1 个材料做汉式 →x₁ false如果一个评审说m3 h1意思是(x₃ true) ∨ (x₁ false)这正是2-SAT 的标准子句形式。3. 建图规则核心对子句(A ∨ B)等价于(¬A → B)(¬B → A)节点编号技巧i材料i做满式i n材料i做汉式那么mX→ 节点XhX→ 节点X n举例评审m3 h1A m3→ 节点 3B h1→ 节点 1n连边¬A → B即3n → 1n¬B → A即1 → 34. 判定是否有解对所有i 1..n如果i和in在同一个强连通分量SCC中 → 矛盾 →BAD否则 → 有解 →GOOD二、为什么这样是对的2-SAT 的本质是逻辑约束 ⇔ 有向图如果i和¬i能互相推导同属一个 SCC说明既必须满式又必须汉式不可能否则按 SCC 拓扑逆序赋值一定存在合法方案三、完整 C 代码Tarjan 版#include bits/stdc.h using namespace std; const int MAXN 210; // n ≤ 100两倍空间 vectorint g[MAXN]; int dfn[MAXN], low[MAXN], scc_id[MAXN]; int stk[MAXN], top, ts, scc_cnt; bool ins[MAXN]; void tarjan(int u) { dfn[u] low[u] ts; stk[top] u; ins[u] true; for (int v : g[u]) { if (!dfn[v]) { tarjan(v); low[u] min(low[u], low[v]); } else if (ins[v]) { low[u] min(low[u], dfn[v]); } } if (low[u] dfn[u]) { scc_cnt; int x; do { x stk[top--]; ins[x] false; scc_id[x] scc_cnt; } while (x ! u); } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int K; cin K; while (K--) { int n, m; cin n m; // 初始化 for (int i 1; i 2 * n; i) { g[i].clear(); dfn[i] low[i] scc_id[i] 0; ins[i] false; } top ts scc_cnt 0; auto get_node [](string s) - int { int id stoi(s.substr(1)); if (s[0] m) return id; // 满式 else return id n; // 汉式 }; for (int i 0; i m; i) { string a, b; cin a b; int u get_node(a); int v get_node(b); // ¬u → v g[u n ? u n : u - n].push_back(v); // ¬v → u g[v n ? v n : v - n].push_back(u); } for (int i 1; i 2 * n; i) { if (!dfn[i]) tarjan(i); } bool ok true; for (int i 1; i n; i) { if (scc_id[i] scc_id[i n]) { ok false; break; } } cout (ok ? GOOD : BAD) \n; } return 0; }缩点DAG例题有一些学校会向其他学校分享软件即如果这个学校得到了软件那么在分享列表中的学校也会得到软件。注意这种关系是单向的即如果 a 在 b 的列表中那么 b 不一定在 a 的列表中。现在你需要向其中一些学校下发新软件。为了节约下发软件的成本你需要回答以下两个问题。至少需要向几个学校下发新软件可以使得所有学校均获得新软件。定义一次扩展为在某个学校的分享列表中增加一个学校。至少需要进行几次扩展才可以使得无论对哪个学校仅下发一次软件就可以使得所有学校获得新软件。两个问题相互独立。输入格式输入文件的第一行包括一个正整数 N表示学校数目。学校的编号为数字 1 到 N。接下来 N 行每行都表示一个分享列表第 i1 行为学校 i 的分享列表中的学校编号。每个列表用 0 结束空列表只用一个 0 表示。输出格式你的程序应该在输出文件中输出两行。第一行应该包括一个正整数表示问题 1 的解。第二行应该包括一个非负整数表示问题 2 的解。一、问题本质建模1. 建图每个学校是一个节点如果学校i能把软件分享给学校j就连一条有向边i → j这样就得到一个有向图。2. 问题翻译问题 1至少向几个学校发软件能让所有学校都收到等价于DAG 中至少选几个起点能到达所有节点答案入度为 0 的 SCC 数量原因在一个 SCC 内部只要有一个点拿到软件整个 SCC 都能拿到缩点后形成 DAG入度为 0 的 SCC 没人能给它传软件必须自己发问题 2至少要加几条边才能让从任意学校发软件所有学校都能收到等价于至少加几条边能让整个图变成强连通图经典结论设a 入度为 0 的 SCC 数量b 出度为 0 的 SCC 数量如果 SCC 数量 1答案 max(a, b)/因为必须让每个scc有入有出才能构成环如果 SCC 数量 1答案 0已经强连通这是 DAG 转强连通的最小加边数公式二、整体解题步骤重点Step 1Tarjan 求 SCCscc_id[i]节点i属于第几个 SCCscc_cntSCC 总数Step 2缩点逻辑上把每个 SCC 看成一个“超级节点”遍历原图所有边(u → v)如果scc_id[u] ! scc_id[v]在 SCC 之间连一条有向边统计每个 SCC 的入度 和出度注意要去重边否则入度/出度会被重复统计Step 3回答问题int a 入度为 0 的 SCC 数量 int b 出度为 0 的 SCC 数量 ans1 a ans2 (scc_cnt 1) ? 0 : max(a, b)三、代码#include bits/stdc.h using namespace std; const int N 110; vectorint g[N]; int dfn[N], low[N], scc_id[N]; int stk[N], top, ts, scc_cnt; bool ins[N]; int in[N], out[N]; // SCC 的入度 / 出度 void tarjan(int u) { dfn[u] low[u] ts; stk[top] u; ins[u] true; for (int v : g[u]) { if (!dfn[v]) { tarjan(v); low[u] min(low[u], low[v]); } else if (ins[v]) { low[u] min(low[u], dfn[v]); } } if (low[u] dfn[u]) { scc_cnt; int x; do { x stk[top--]; ins[x] false; scc_id[x] scc_cnt; } while (x ! u); } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; for (int i 1; i n; i) { int x; while (cin x x) { g[i].push_back(x); } } // Tarjan 求 SCC for (int i 1; i n; i) { if (!dfn[i]) tarjan(i); } // 特判已经强连通 if (scc_cnt 1) { cout 1\n0\n; return 0; } // 统计 SCC 的入度和出度 for (int u 1; u n; u) { for (int v : g[u]) { int a scc_id[u], b scc_id[v]; if (a ! b) { out[a]; in[b]; } } } int a 0, b 0; for (int i 1; i scc_cnt; i) { if (in[i] 0) a; if (out[i] 0) b; } cout a \n max(a, b) \n; return 0; }
