1.二分图匹配

• 洛谷题目：P3386 二分图最大匹配

• 参考视频：https://www.bilibili.com/video/BV1GW4y1z7xk/

题目描述

给定一个二分图，其左部点的个数为 $n$，右部点的个数为 $m$，边数为 $e$，求其最大匹配的边数。

左部点从 $1$ 至 $n$ 编号，右部点从 $1$ 至 $m$ 编号。

输入格式

输入的第一行是三个整数，分别代表 $n$，$m$ 和 $e$。

接下来 $e$ 行，每行两个整数 $u, v$，表示存在一条连接左部点 $u$ 和右部点 $v$ 的边。

输出格式

输出一行一个整数，代表二分图最大匹配的边数。

输入输出样例 #1

输入 #1

1 1 1
1 1

输出 #1

1

输入输出样例 #2

输入 #2

4 2 7
3 1
1 2
3 2
1 1
4 2
4 1
1 1

输出 #2

2

说明/提示

数据规模与约定

对于全部的测试点，保证：

• $1 \leq n, m \leq 500$。

• $1 \leq e \leq 5 \times 10^4$。

• $1 \leq u \leq n$，$1 \leq v \leq m$。

不保证给出的图没有重边。

1.1. 匈牙利算法的核心概念

• 增广路：从一个未匹配的左节点出发，交替经过 “未匹配边 - 匹配边”，最终到达一个未匹配的右节点的路径。找到增广路后，翻转路径上的匹配状态（未匹配→匹配，匹配→未匹配），可使总匹配数 + 1。

• vis 数组：单次 DFS 中标记已访问的右节点，避免同一节点被重复尝试（比如：男生 A 尝试匹配女生 1，女生 1 已匹配男生 B，递归让男生 B 找其他女生时，不能再尝试女生 1，否则死循环）。

• match 数组：记录右节点的匹配状态，是算法的核心状态载体。

1.2. 算法执行流程

1. 对每个左节点（男生），初始化 vis 数组后调用 DFS；

2. DFS 遍历该男生能匹配的所有女生：

   • 若女生未被访问，标记后尝试匹配；

   • 女生未匹配→直接配对；女生已匹配→递归让其当前配对的男生 “让贤”；

3. 每成功匹配一次，总匹配数 ans+1；

4. 遍历完所有左节点后，ans 即为最大匹配数。

1.3. 关键细节

• 二分图的边是单向的（左→右），无需处理反向边；

• vis 数组必须每次 DFS 前清空，因为每个左节点的匹配尝试是独立的；

• match 数组初始为 0，表示所有右节点未匹配。

1.4. 适用场景

该算法适用于二分图最大匹配问题（如：人员分配、选课匹配、棋盘覆盖等），是解决此类问题的经典算法，实现简单且在数据规模适中时效率足够（本题 n≤500，完全适配）。

参考代码

#include <bits/stdc++.h>
using namespace std;

// 常量定义：
// N：左集合（男生）的最大节点数（505）；M：边的最大数量（1e5，适配链式前向星）
const int N = 505, M = 100010;

// 全局变量
int n, m, k;       // n：左集合节点数（男生数量）；m：右集合节点数（女生数量）；k：边的数量
int a, b, ans;     // a/b：临时存储边的两个端点；ans：最大匹配数（最终答案）

// 链式前向星的边结构体：存储二分图的边（仅从左集合指向右集合）
struct edge
{
    int v, ne;     // v：边的终点（右集合节点/女生）；ne：下一条边的索引（链式前向星）
} e[M];            // e[]：存储所有边

// 链式前向星核心变量
int h[N], idx;     // h[u]：左集合节点u的邻接表头指针；idx：边的索引计数器（加边用）

// 匹配相关数组
int vis[N];        // vis[v]：标记右集合节点v是否被访问过（单次找增广路时，避免重复访问）
int match[N];      // match[v]：记录右集合节点v当前匹配的左集合节点（女生v对应的男生）

// 链式前向星加边函数：添加左集合a到右集合b的边（二分图单向边）
void add(int a, int b)
{
    e[++idx] = {b, h[a]};  // 新建边：终点为b，下一条边为当前h[a]指向的边
    h[a] = idx;            // 更新a的邻接表头为当前新边的索引
}

// 深度优先搜索（DFS）：为左集合节点u寻找增广路（匹配右集合节点）
// 返回值：1表示找到可匹配的节点，0表示未找到
bool dfs(int u)
{
    // 遍历u的所有邻接边（u能匹配的所有女生）
    for (int i = h[u]; i; i = e[i].ne)
    {
        int v = e[i].v;    // v：当前遍历到的右集合节点（女生）
        
        if (vis[v]) continue;  // 若v已被访问过，跳过（避免重复尝试，防止死循环）
        vis[v] = 1;            // 标记v为已访问（单次DFS中不再处理）
        
        // 匹配逻辑：
        // 1. 若v未匹配（match[v]=0），直接将v匹配给u；
        // 2. 若v已匹配，递归尝试让v的当前匹配对象（match[v]）找其他女生，若成功则v可匹配给u
        if (!match[v] || dfs(match[v]))
        {
            match[v] = u;  // 将v匹配给u（更新匹配关系）
            return 1;      // 匹配成功，返回1
        }
    }
    return 0;  // 遍历完所有邻接节点都无法匹配，返回0
}

int main()
{
    // 第一步：读入左集合大小n、右集合大小m、边数k
    cin >> n >> m >> k;
    
    // 第二步：读入k条边，构建二分图（链式前向星）
    for (int i = 0; i < k; i++)
    {
        cin >> a >> b;     // a：左集合节点（男生），b：右集合节点（女生）
        add(a, b);         // 添加a→b的边
    }
    
    // 第三步：对每个左集合节点，尝试寻找匹配（匈牙利算法核心）
    for (int i = 1; i <= n; i++)
    {
        memset(vis, 0, sizeof vis);  // 每次DFS前清空访问标记（每个男生的尝试独立）
        if (dfs(i)) ans++;           // 若i匹配成功，最大匹配数+1
    }
    
    // 第四步：输出最大匹配数
    cout << ans;
    return 0;
}

2.网络流

• 洛谷题目：P3376 网络最大流

• 参考视频：https://www.bilibili.com/video/BV18F411c7M1/

题目描述

如题，给出一个网络图，以及其源点和汇点，求出其网络最大流。

输入格式

第一行包含四个正整数 $n,m,s,t$，分别表示点的个数、有向边的个数、源点序号、汇点序号。

接下来 $m$ 行每行包含三个正整数 $u_i,v_i,w_i$，表示第 $i$ 条有向边从 $u_i$ 出发，到达 $v_i$，边权为 $w_i$（即该边最大流量为 $w_i$）。

输出格式

一行，包含一个正整数，即为该网络的最大流。

输入输出样例 #1

输入 #1

4 5 4 3
4 2 30
4 3 20
2 3 20
2 1 30
1 3 30

输出 #1

50

数据规模与约定

• 对于 $30\%$ 的数据，保证 $n\leq10$，$m\leq25$。

• 对于 $100\%$ 的数据，保证 $1 \leq n\leq200$，$1 \leq m\leq 5000$，$0 \leq w\lt 2^{31}$。

2.1. 网络流核心概念

• 增广路：从源点 S 到汇点 T 的一条路径，路径上所有边的剩余容量 > 0，沿该路径可增加流量；

• 反向边：用于 “反悔” 操作（退流），允许算法撤销错误的增广选择，是网络流算法的核心；

• 分层图：BFS 按 “到源点的最短距离（边数）” 分层，保证 DFS 只沿 “层数 + 1” 的方向遍历，避免环和无效路径。

2.2. 三大优化策略

优化策略	作用
当前弧优化	记录节点的遍历位置，避免重复遍历已无剩余容量的边，减少 DFS 时间；
余量优化	当节点的剩余可分配流量为 0 时，直接退出遍历，避免无效递归；
残枝优化	清空无流出流量的节点层数，后续 BFS 不再处理该节点，减少分层时间；

2.3. 关键细节

• idx 从 1 开始：反向边通过i^1获取（如正向边索引 2→反向边 3，4→5），若 idx 从 0 开始，0^1=1会破坏成对关系；

• 反向边初始容量为 0：初始无退流能力，仅当正向边有增广流量时，反向边才获得容量；

• min(mf, e[i].c)：增广流量受限于 “节点剩余流量” 和 “边的剩余容量”，取较小值保证合法性。

2.4. 算法执行流程

1. BFS 构建分层图，判断是否存在增广路；

2. 若存在，重置当前弧指针，调用 DFS 从 S 开始多路增广；

3. DFS 沿分层图方向遍历，计算增广流量并更新边的剩余容量；

4. 重复 1~3 直到无增广路，累加的总流量即为最大流。

2.5. 适用场景

Dinic 算法是求解网络最大流的首选算法，适用于大多数网络流问题（如最大匹配、最小割、上下界网络流等），优化后在实际应用中效率极高。

参考代码

#include <bits/stdc++.h>
#define LL long long          // 定义长整型，避免流量溢出
#define N 10010              // 节点最大数量
#define M 200010             // 边的最大数量（正向+反向边，需开2倍）
using namespace std;

// 全局变量
int n, m, S, T;               // n：节点数；m：边数；S：源点；T：汇点

// 链式前向星的边结构体（存储网络流的边信息）
struct edge
{
    LL v;                     // 边的终点（目标节点）
    LL c;                     // 边的剩余容量（核心：初始为容量，增广后减少）
    int ne;                   // 下一条边的索引（链式前向星）
} e[M];                       // e[]：存储所有边（正向+反向）

// 链式前向星核心变量
int h[N], idx = 1;            // h[u]：节点u的邻接表头指针；idx=1（关键！反向边用i^1，保证正向/反向边成对：2&3、4&5...）
int d[N];                     // d[u]：节点u在分层图中的层数（梯度），用于BFS分层
int cur[N];                   // cur[u]：节点u的当前弧指针（当前弧优化，避免重复遍历无效边）

// 链式前向星加边函数：添加正向边和反向边（网络流必备）
// a：起点；b：终点；c：正向边的初始容量（反向边容量为0）
void add(int a, int b, int c)
{
    e[++idx] = {b, c, h[a]};  // 添加正向边：终点b，容量c，下一条边为h[a]
    h[a] = idx;               // 更新a的邻接表头为当前正向边索引
}

// BFS函数：构建分层图（梯度图），判断是否存在从S到T的增广路
// 返回值：true=存在增广路，false=无增广路（算法终止）
bool bfs()
{
    memset(d, 0, sizeof d);   // 初始化所有节点的层数为0（未分层）
    queue<int> q;
    q.push(S);                // 源点入队，作为分层起点
    d[S] = 1;                 // 源点层数设为1（梯度初始值）
    
    while (q.size())
    {
        int u = q.front();
        q.pop();
        
        // 遍历u的所有邻边
        for (int i = h[u]; i; i = e[i].ne)
        {
            int v = e[i].v;   // 边的终点v
            // 分层条件：v未分层（d[v]=0）且边有剩余容量（e[i].c>0）
            if (d[v] == 0 && e[i].c)
            {
                d[v] = d[u] + 1;  // v的层数=u的层数+1（梯度+1）
                q.push(v);        // v入队，继续分层
                if (v == T) return true; // 直接找到汇点，提前返回（存在增广路）
            }
        }
    }
    return false;  // 遍历完所有可达节点仍未到T，无增广路
}

// DFS函数：多路增广，在分层图中寻找增广路并计算流量
// u：当前遍历节点；mf：当前节点可分配的最大剩余流量（余量）
// 返回值：从u到T的实际增广流量
LL dfs(int u, LL mf)
{
    if (u == T) return mf;    // 到达汇点，返回剩余流量（全部可作为增广流量）
    
    LL sum = 0;               // sum：当前节点u实际流出的总流量
    // 遍历u的邻边（从当前弧cur[u]开始，避免重复遍历无效边）
    for (int i = cur[u]; i; i = e[i].ne)
    {
        cur[u] = i;           // 当前弧优化：记录u的当前遍历位置，下次直接从该位置开始
        int v = e[i].v;       // 边的终点v
        
        // 增广条件：v的层数=u的层数+1（符合分层图）且边有剩余容量
        if (d[v] == d[u] + 1 && e[i].c)
        {
            // 递归计算v到T的增广流量：取“u的剩余流量”和“边的剩余容量”的较小值
            LL f = dfs(v, min(mf, e[i].c));
            
            // 后序更新：调整边的剩余容量（网络流核心）
            e[i].c -= f;      // 正向边剩余容量 -= 增广流量
            e[i ^ 1].c += f;  // 反向边剩余容量 += 增广流量（用于反悔，退流）
            
            sum += f;         // 累加u的流出流量
            mf -= f;          // 余量优化：减少u的剩余可分配流量
            if (mf == 0) break; // 无剩余流量，直接退出（无需继续遍历）
        }
    }
    
    // 残枝优化：若u无流出流量，说明该节点在当前分层图中无贡献，清空层数（后续BFS不再处理）
    if (sum == 0) d[u] = 0;
    return sum;               // 返回u的实际流出总流量
}

// Dinic算法主函数：循环BFS分层 + DFS增广，累加所有增广流量得到最大流
LL dinic()
{
    LL flow = 0;              // flow：总最大流
    while (bfs())             // 只要存在增广路（分层图可达T）
    {
        memcpy(cur, h, sizeof h); // 重置当前弧指针（初始化为邻接表头）
        flow += dfs(S, 1e9);  // 从源点S开始多路增广，初始余量设为极大值（1e9）
    }
    return flow;              // 返回最大流
}

int main()
{
    int a, b, c;
    // 读入：节点数n、边数m、源点S、汇点T
    scanf("%d%d%d%d", &n, &m, &S, &T);
    
    // 读入m条边，构建网络流图（正向+反向边）
    while (m--)
    {
        scanf("%d%d%d", &a, &b, &c); // a：起点，b：终点，c：容量
        add(a, b, c);               // 添加正向边（容量c）
        add(b, a, 0);               // 添加反向边（容量0，idx自动成对）
    }
    
    // 计算并输出最大流
    printf("%lld\n", dinic());
    return 0;
}

3.费用流

• 洛谷题目：P3381 最小费用最大流

• 参考视频：https://www.bilibili.com/video/BV1SU4y1D77p/

题目描述

给出一个包含 $n$ 个点和 $m$ 条边的有向图（下面称其为网络） $G=(V,E)$，该网络上所有点分别编号为 $1 \sim n$，所有边分别编号为 $1\sim m$，其中该网络的源点为 $s$，汇点为 $t$，网络上的每条边 $(u,v)$ 都有一个流量限制 $w(u,v)$ 和单位流量的费用 $c(u,v)$。

你需要给每条边 $(u,v)$ 确定一个流量 $f(u,v)$，要求：

1. $0 \leq f(u,v) \leq w(u,v)$（每条边的流量不超过其流量限制）；

2. $\forall p \in \{V \setminus \{s,t\}\}$，$\sum_{(i,p) \in E}f(i,p)=\sum_{(p,i)\in E}f(p,i)$（除了源点和汇点外，其他各点流入的流量和流出的流量相等）；

3. $\sum_{(s,i)\in E}f(s,i)=\sum_{(i,t)\in E}f(i,t)$（源点流出的流量等于汇点流入的流量）。

定义网络 $G$ 的流量 $F(G)=\sum_{(s,i)\in E}f(s,i)$，网络 $G$ 的费用 $C(G)=\sum_{(i,j)\in E} f(i,j) \times c(i,j)$。

你需要求出该网络的最小费用最大流，即在 $F(G)$ 最大的前提下，使 $C(G)$ 最小。

输入格式

输入第一行包含四个整数 $n,m,s,t$，分别代表该网络的点数 $n$，网络的边数 $m$，源点编号 $s$，汇点编号 $t$。

接下来 $m$ 行，每行四个整数 $u_i,v_i,w_i,c_i$，分别代表第 $i$ 条边的起点，终点，流量限制，单位流量费用。

输出格式

输出两个整数，分别为该网络的最大流 $F(G)$，以及在 $F(G)$ 最大的前提下，该网络的最小费用 $C(G)$。

输入输出样例 #1

输入 #1

4 5 4 3
4 2 30 2
4 3 20 3
2 3 20 1
2 1 30 9
1 3 40 5

输出 #1

50 280

说明/提示

对于 $100\%$ 的数据，$1 \leq n \leq 5\times 10^3$，$1 \leq m \leq 5 \times 10^4$，$1 \leq s,t \leq n$，$u_i \neq v_i$，$0 \leq w_i,c_i \leq 10^3$，且该网络的最大流和最小费用 $\leq 2^{31}-1$。

输入数据随机生成。

3.1. 费用流核心概念

• 最小费用增广路：在剩余网络中，从 S 到 T 的路径中，单位流量的总费用最小的路径（以费用为边权的最短路）；

• 反向边：费用流的反向边不仅容量可逆，单位费用为正向边的相反数（退流时抵消原费用，保证费用计算正确）；

• mf[T]：增广路的最大可行流量（由路径上最小剩余容量决定），也是本次增广的流量。

3.2. SPFA 的核心作用

SPFA 替代了普通最大流 EK 算法中的 BFS，核心目标从 “找任意增广路” 变为 “找最小费用增广路”：

• d[v] 维护 S 到 v 的最小费用（最短路）；

• mf[v] 维护 S 到 v 的最大可行流量；

• pre[v] 记录增广路的前驱边，用于后续回溯更新容量。

3.3. 关键细节

• idx 从 1 开始：反向边通过 i^1 获取（如正向边 2→反向边 3，4→5），保证正向 / 反向边成对；

• 反向边费用为 - d：退流时（反向边增流），费用会减去对应值，抵消原正向边的费用，保证费用计算的正确性；

• mf[S] = INF：源点初始无流量限制，增广路的流量由路径上的最小容量决定（mf[v] = min(mf[u], c)）。

3.4. 算法执行流程

1. SPFA 找 S 到 T 的最小费用增广路，记录增广路的流量（mf [T]）和费用（d [T]）；

2. 回溯增广路，更新正向 / 反向边的剩余容量；

3. 累加总流量（flow）和总费用（cost = 流量 × 单位费用）；

4. 重复 1~3 直到无增广路，此时 flow 是最大流，cost 是最大流对应的最小费用。

3.5. 适用场景

该算法适用于小规模最小费用最大流问题（节点数≤5000），如：带费用的网络流分配、物流路径优化（最小成本运输最大货物）等场景。若数据规模较大，可替换为 Dinic 优化的费用流（分层 + 多路增广）。

参考代码

#include <bits/stdc++.h>
using namespace std;

// 常量定义：
// N：节点最大数量；M：边的最大数量（正向+反向边，需开2倍）；INF：流量/费用的无穷大值
const int N = 5010, M = 100010, INF = 1e8;

// 全局变量
int n, m, S, T;               // n：节点数；m：边数；S：源点；T：汇点

// 链式前向星的边结构体（费用流专用，新增单位费用w）
struct edge
{
    int v;                     // 边的终点
    int c;                     // 边的剩余容量（核心：初始为容量，增广后减少）
    int w;                     // 边的单位费用（每流过1单位流量的费用）
    int ne;                    // 下一条边的索引（链式前向星）
} e[M];                       // e[]：存储所有边（正向+反向）

// 链式前向星核心变量
int h[N], idx = 1;            // h[u]：节点u的邻接表头指针；idx=1（关键！反向边用i^1，保证正向/反向边成对：2&3、4&5...）

// 费用流核心状态数组
int d[N];                     // d[v]：从源点S到节点v的最小费用（最短路径长度）
int mf[N];                    // mf[v]：从源点S到节点v的最大可行流量（增广路中v点能通过的最大流量）
int pre[N];                   // pre[v]：记录到达v的增广路中，最后一条边的索引（用于回溯增广路）
int vis[N];                   // vis[v]：SPFA的访问标记（避免节点重复入队）
int flow, cost;               // flow：总最大流；cost：总最小费用（最大流前提下）

// 链式前向星加边函数：添加费用流的正向边和反向边
// a：起点；b：终点；c：正向边初始容量；d：正向边单位费用（反向边费用为-d）
void add(int a, int b, int c, int d)
{
    e[++idx] = {b, c, d, h[a]};  // 添加正向边：终点b，容量c，单位费用d，下一条边为h[a]
    h[a] = idx;                  // 更新a的邻接表头为当前正向边索引
}

// SPFA函数：寻找从S到T的「最小费用增广路」（以费用为边权的最短路）
// 返回值：true=存在增广路（mf[T]>0），false=无增广路（算法终止）
bool spfa()
{
    memset(d, 0x3f, sizeof d);   // 初始化最小费用为无穷大（0x3f3f3f3f ≈ 1e9，适配int范围）
    memset(mf, 0, sizeof mf);    // 初始化最大可行流量为0
    queue<int> q;
    
    q.push(S);                   // 源点入队，作为最短路起点
    d[S] = 0;                    // 源点到自身的费用为0
    mf[S] = INF;                 // 源点的最大可行流量为无穷大（初始无限制）
    vis[S] = 1;                  // 标记源点已入队
    
    while (q.size())
    {
        int u = q.front();
        q.pop();
        vis[u] = 0;              // 出队后取消标记，允许再次入队（SPFA松弛特性）
        
        // 遍历u的所有邻边
        for (int i = h[u]; i; i = e[i].ne)
        {
            int v = e[i].v;      // 边的终点v
            int c = e[i].c;      // 边的剩余容量
            int w = e[i].w;      // 边的单位费用
            
            // 松弛条件：v的当前最小费用 > u的费用+边费用，且边有剩余容量（c>0）
            if (d[v] > d[u] + w && c)
            {
                d[v] = d[u] + w; // 更新v的最小费用（最短路松弛）
                pre[v] = i;      // 记录到达v的最后一条边的索引（用于回溯增广路）
                mf[v] = min(mf[u], c); // 更新v的最大可行流量（取u的流量和边容量的较小值）
                
                if (!vis[v])     // 未入队则入队，避免重复处理
                {
                    q.push(v);
                    vis[v] = 1;
                }
            }
        }
    }
    return mf[T] > 0; // 若汇点T的最大可行流量>0，说明存在增广路
}

// EK算法主逻辑：循环找最小费用增广路，更新流量和费用
void EK()
{
    while (spfa()) // 只要存在最小费用增广路
    {
        // 回溯增广路（从汇点T到源点S），更新边的剩余容量
        for (int v = T; v != S;)
        {
            int i = pre[v];      // 到达v的前驱边索引
            e[i].c -= mf[T];     // 正向边剩余容量 -= 增广流量（mf[T]是增广路的最大可行流量）
            e[i ^ 1].c += mf[T]; // 反向边剩余容量 += 增广流量（费用流反向边用于退流/反悔）
            v = e[i ^ 1].v;      // 回溯到前驱节点（反向边的终点=正向边的起点）
        }
        
        flow += mf[T];           // 累加总最大流（本次增广的流量）
        cost += mf[T] * d[T];    // 累加总最小费用（流量 × 单位费用）
    }
}

int main()
{
    // 读入：节点数n、边数m、源点S、汇点T
    scanf("%d%d%d%d", &n, &m, &S, &T);
    int a, b, c, d;
    
    // 读入m条边，构建费用流图（正向+反向边）
    while (m--)
    {
        scanf("%d%d%d%d", &a, &b, &c, &d); // a：起点，b：终点，c：容量，d：单位费用
        add(a, b, c, d);                  // 添加正向边（容量c，费用d）
        add(b, a, 0, -d);                 // 添加反向边（容量0，费用-d：费用流反向边费用为相反数）
    }
    
    EK(); // 求解最小费用最大流
    
    // 输出：最大流 + 最大流对应的最小费用
    printf("%d %d\n", flow, cost);
    return 0;
}

4.强连通分量

• 洛谷题目：P2863 The Cow Prom S

• 参考视频：https://www.bilibili.com/video/BV1SY411M7Tv/

题目描述

有一个 $n$ 个点，$m$ 条边的有向图，请求出这个图点数大于 $1$ 的强连通分量个数。

输入格式

第一行为两个整数 $n$ 和 $m$。

第二行至 $m+1$ 行，每一行有两个整数 $a$ 和 $b$，表示有一条从 $a$ 到 $b$ 的有向边。

输出格式

仅一行，表示点数大于 $1$ 的强连通分量个数。

输入输出样例 #1

输入 #1

5 4
2 4
3 5
1 2
4 1

输出 #1

1

说明/提示

数据规模与约定

对于全部的测试点，保证 $2\le n \le 10^4$，$2\le m\le 5\times 10^4$，$1 \leq a, b \leq n$。

4.1. Tarjan 算法的核心思想

• 时间戳（dfn）：标记节点首次被 DFS 访问的顺序，保证每个节点的 dfn 唯一且递增；

• 追溯值（low）：标记节点能到达的最早祖先（栈内节点），体现 “强连通” 的核心（互相可达）；

• 栈：维护当前 DFS 路径上的节点，保证 SCC 的 “极大性”（弹出的节点构成不可再扩展的强连通子图）。

4.2. SCC 的判定条件

当 dfn[x] == low[x] 时，说明：

• 节点 x 无法通过任何边到达比自身更早访问的节点（除了栈内的节点）；

• 栈中从 x 到栈顶的所有节点构成一个强连通分量（这些节点互相可达，且无法包含更多节点）。

4.3. 关键细节

• !scc[y] 的判断：确保 y 未被归入任何 SCC（仍在栈中），避免将已弹出栈的节点纳入当前 SCC；

• 非连通图处理：主函数遍历所有节点，对未访问的节点调用 Tarjan，保证所有连通分量都被处理；

• 统计逻辑：siz[i] > 1 表示该 SCC 包含至少两个节点（存在环），是题目要求的统计目标。

4.4. 算法时间复杂度

Tarjan 算法是线性的 (O(n+m))：每个节点仅被访问一次（DFS），每条边仅被遍历一次（邻接表遍历），栈操作的总次数为 O (n)（每个节点入栈 / 出栈各一次）。

4.5. 适用场景

Tarjan 算法是求解有向图强连通分量的经典算法，可用于：

• 缩点（将 SCC 缩为单个节点，将有向图转为 DAG）；

• 判定有向图是否存在环；

• 求解强连通分量的数量 / 大小、最大 SCC 等问题。

参考代码

// Tarjan算法 求解有向图强连通分量（SCC），时间复杂度 O(n+m)
#include<bits/stdc++.h>
using namespace std;

// 常量定义：节点最大数量（适配题目数据范围）
const int N = 10010;

// 全局变量
int n, m, a, b, ans;          // n：节点数；m：边数；a/b：临时存储边的端点；ans：大小>1的SCC数量
vector<int> e[N];             // 邻接表：e[x]存储节点x的所有出边指向的节点（有向边）

// Tarjan算法核心状态变量
int dfn[N];                   // dfn[x]：节点x的时间戳（首次被DFS访问的顺序编号）
int low[N];                   // low[x]：节点x能追溯到的最早时间戳（x或x的子树能到达的最早祖先节点的dfn）
int tim;                      // 时间戳计数器（全局递增，标记访问顺序）
int stk[N], top;              // stk[]：栈，存储当前DFS路径上的节点；top：栈顶指针（初始为0）
int scc[N];                   // scc[x]：节点x所属的强连通分量编号（1~cnt）
int siz[N];                   // siz[cnt]：编号为cnt的SCC包含的节点数量
int cnt;                      // SCC的计数器（统计有多少个SCC）

// Tarjan算法核心函数：递归遍历节点x，计算dfn/low，识别SCC
void tarjan(int x)
{
    // 第一步：初始化当前节点的时间戳和追溯值（首次访问）
    dfn[x] = low[x] = ++tim;
    // 第二步：将x入栈（当前DFS路径的节点都入栈，用于后续提取SCC）
    stk[++top] = x;

    // 第三步：遍历x的所有出边（递归处理子节点）
    for (int y : e[x])
    {
        if (!dfn[y])  // 情况1：y未被访问过（未分配时间戳）
        {
            tarjan(y);  // 递归遍历y
            // 回溯时更新x的low值：x的追溯值 = min(自身low, 子节点y的low)
            // 原因：y是x的子节点，y能到达的最早祖先，x也能到达
            low[x] = min(low[x], low[y]);
        }
        else if (!scc[y])  // 情况2：y已访问（有dfn）但未归属任何SCC（仍在栈中）
        {
            // 更新x的low值：x的追溯值 = min(自身low, y的dfn)
            // 原因：y是x的祖先/同层节点，且在当前DFS路径中（栈内），x可通过y到达更早的节点
            low[x] = min(low[x], dfn[y]);
        }
    }

    // 第四步：判断x是否是某个SCC的根节点（dfn[x] == low[x]）
    if (dfn[x] == low[x])
    {
        cnt++;  // 新增一个SCC，编号+1
        // 出栈：从栈顶到x的所有节点属于当前SCC
        for (int y = -1; y != x;)  // 循环直到弹出x（y==x时终止）
        {
            y = stk[top--];  // 栈顶节点出栈，赋值给y
            scc[y] = cnt;    // 标记y属于第cnt个SCC
            siz[cnt]++;      // 第cnt个SCC的大小+1
        }
    }
}

int main()
{
    // 加速输入输出（关闭同步，避免cin/cout超时）
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    // 第一步：读入节点数n和边数m
    cin >> n >> m;
    // 第二步：读入m条有向边，构建邻接表
    while (m--)
    {
        cin >> a >> b;
        e[a].push_back(b);  // 添加有向边a→b
    }

    // 第三步：对所有未访问的节点执行Tarjan（处理非连通的有向图）
    for (int i = 1; i <= n; i++)
    {
        if (!dfn[i])  // 节点i未被访问（无时间戳）
            tarjan(i);
    }

    // 第四步：统计大小>1的SCC数量（强连通分量内节点数>1，即存在环）
    for (int i = 1; i <= cnt; i++)
    {
        if (siz[i] > 1)
            ans++;
    }

    // 输出结果：大小>1的SCC数量
    cout << ans;
    return 0;
}

5.2-SAT问题

• 洛谷题目：P4782 2-SAT问题

• 参考视频：https://www.bilibili.com/video/BV1kE421w7XR/

题目描述

有 $n$ 个布尔变量 $x_1\sim x_n$，另有 $m$ 个需要满足的条件，每个条件的形式都是 「$x_i$ 为 true / false 或 $x_j$ 为 true / false」。比如 「$x_1$ 为真或 $x_3$ 为假」、「$x_7$ 为假或 $x_2$ 为假」。

2-SAT 问题的目标是给每个变量赋值使得所有条件得到满足。

输入格式

第一行两个整数 $n$ 和 $m$，意义如题面所述。

接下来 $m$ 行每行 $4$ 个整数 $i$, $a$, $j$, $b$，表示 「$x_i$ 为 $a$ 或 $x_j$ 为 $b$」($a, b\in \{0,1\}$)

输出格式

如无解，输出 IMPOSSIBLE；

否则输出 POSSIBLE，下一行 $n$ 个整数 $x_1\sim x_n$（$x_i\in\{0,1\}$），表示构造出的解。

输入输出样例 #1

输入 #1

3 1
1 1 3 0

输出 #1

POSSIBLE
0 0 0

说明/提示

$1\leq n, m\leq 10^6$ , 前 $3$ 个点卡小错误，后面 $5$ 个点卡效率。

由于数据随机生成，可能会含有 10 0 10 0 之类的坑，但按照最常规写法的写的标程没有出错，各个数据点卡什么的提示在标程里。

2-SAT 问题 的经典解法（Tarjan 找强连通分量），时间复杂度 $O(n+m)$，核心解决： 给定 n 个布尔变量 $x_1,x_2,...,x_n$，m 个形如「$x_i$ 取 a 或 $x_j$ 取 b」的逻辑约束（a/b 为 0/1，表示假/真），判断是否存在变量赋值满足所有约束；若存在则输出一组可行解，否则输出“IMPOSSIBLE”。

2-SAT 的核心思路是将每个布尔变量拆为两个节点（对应“取假”/“取真”），将逻辑约束转化为有向边，通过 Tarjan 找强连通分量（SCC）：若某变量的两个节点属于同一 SCC，则无解；否则根据 SCC 编号大小输出可行解。

5.1. 2-SAT 的节点编码与约束转化

节点含义	编码	说明
$x_i$ 取 0（假）	$i$	基础节点
$x_i$ 取 1（真）	$i + n$	每个变量拆为两个节点

逻辑约束「$x_i$ 取 a 或 $x_j$ 取 b」的转化规则： “或”的逻辑等价于「若 $x_i$ 不取 a，则 $x_j$ 必须取 b」且「若 $x_j$ 不取 b，则 $x_i$ 必须取 a」，对应两条有向边：

• $i + !a \times n \rightarrow j + b \times n$（非A→B）

• $j + !b \times n \rightarrow i + a \times n$（非B→A）

5.2. 无解判定规则

若某变量 $x_i$ 的两个节点（$i$ 和 $i+n$）属于同一SCC，说明「$x_i$ 取0」和「$x_i$ 取1」互相推导（矛盾），因此不存在可行赋值。

5.3. 可行解的赋值规则

SCC 的编号对应 DAG 拓扑序的逆序（Tarjan 算法弹出SCC的顺序是拓扑逆序）：

• 若 $scc[i] > scc[i+n]$：选择 $x_i$ 取1（真）；

• 若 $scc[i] < scc[i+n]$：选择 $x_i$ 取0（假）。 原理：拓扑序中“更晚”的节点（编号大）优先满足，避免约束冲突。

5.4. 时间复杂度

Tarjan 算法是线性的 $O(n+m)$（$n$ 为变量数，$m$ 为约束数），2-SAT 的建图和判定过程均为线性，因此整体复杂度为 $O(n+m)$。

5.5. 适用场景

2-SAT 是解决布尔变量逻辑约束问题的经典算法，可适配多种约束形式（如“$x_i$ 取a → $x_j$ 取b”、“$x_i$ 与 $x_j$ 不能同时为真”等），只需将约束转化为对应的有向边即可。

参考代码

// 2-SAT问题 + Tarjan算法求解强连通分量（SCC），时间复杂度 O(n+m)
#include<bits/stdc++.h>
using namespace std;

// 常量定义：节点最大数量（每个布尔变量拆为2个节点，故开2*n的空间，此处N=2e6适配题目范围）
const int N = 2000005;

// 全局变量
int n, m;                      // n：布尔变量数量；m：逻辑约束数量
// 链式前向星（存储有向图，用于2-SAT的约束转化）
int hd[N]; //节点x的邻接表头指针；
int to[N]; //边idx的终点；
int ne[N]; //边idx的下一条边；
int idx;  //边计数器（初始0）
// Tarjan算法核心状态（与强连通分量求解一致）
int dfn[N];                    // dfn[x]：节点x的时间戳（首次访问顺序）
int low[N];                    // low[x]：x能追溯到的最早时间戳（SCC判定核心）
int tim;                       // 时间戳计数器
int stk[N], top;                 // stk[]：存储当前DFS路径的节点栈；top：栈顶指针
int scc[N];                    // scc[x]：节点x所属的SCC编号
int cnt;                      // SCC的总数量

// 链式前向星加边函数：添加有向边 a → b
void add(int a, int b)
{
    to[++idx] = b;             // 边的终点为b
    ne[idx] = hd[a];           // 下一条边指向当前a的表头
    hd[a] = idx;               // 更新a的表头为当前边索引
}

// Tarjan算法：递归遍历节点x，求解SCC（逻辑与标准Tarjan一致）
void tarjan(int x)
{
    dfn[x] = low[x] = ++tim;   // 初始化时间戳和追溯值
    stk[++top] = x;            // 节点入栈（维护当前DFS路径）
    
    // 遍历x的所有出边
    for (int i = hd[x]; i; i = ne[i])
    {
        int y = to[i];         // 边的终点y
        if (!dfn[y])           // y未被访问，递归处理
        {
            tarjan(y);
            low[x] = min(low[x], low[y]); // 回溯更新x的追溯值
        }
        else if (!scc[y])      // y已访问但未归属SCC（仍在栈中）
            low[x] = min(low[x], dfn[y]); // 更新x的追溯值
    }
    
    // 判定x是SCC的根节点（dfn[x] == low[x]），提取该SCC
    if (low[x] == dfn[x])
    {
        ++cnt;                 // SCC编号+1
        // 出栈：从栈顶到x的所有节点归为当前SCC
        for (int y = -1; y != x;)
        {
            y = stk[top--];    // 栈顶节点出栈
            scc[y] = cnt;      // 标记y的SCC编号
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);     // 输入：变量数n，约束数m
    
    // 处理每个逻辑约束：约束形式为「x_i取a 或 x_j取b」（a,b∈{0,1}）
    for (int i, a, j, b; m--;)
    {
        scanf("%d%d%d%d", &i, &a, &j, &b);
        // 2-SAT核心：将「A或B」转化为「非A→B 且 非B→A」
        // 节点编码规则：
        // - i 表示「x_i取0（假）」，i+n 表示「x_i取1（真）」
        // !a 表示「x_i不取a」，对应节点为 i + !a * n；b表示「x_j取b」，对应节点 j + b * n
        add(i + !a * n, j + b * n); // 非A→B：x_i不取a → x_j必须取b
        add(j + !b * n, i + a * n); // 非B→A：x_j不取b → x_i必须取a
    }
    
    // 对所有节点（1~2n）执行Tarjan，求解所有SCC（处理非连通图）
    for (int i = 1; i <= 2 * n; i++)
        if (!dfn[i]) tarjan(i);
    
    // 判定2-SAT是否有解：若某变量x_i的两个节点（i和i+n）属于同一SCC，则无解
    for (int i = 1; i <= n; i++)
    {
        if (scc[i] == scc[i + n])
        {
            puts("IMPOSSIBLE"); // 输出无解
            return 0;
        }
    }
    
    // 有解：输出可行赋值
    puts("POSSIBLE");
    // 赋值规则：scc[i] > scc[i+n] 时，x_i取1（真）；否则取0（假）
    // 原理：SCC编号对应拓扑序逆序，编号大的节点在拓扑序中更“晚”，优先选择
    for (int i = 1; i <= n; i++)
        printf("%d ", scc[i] > scc[i + n]);
    
    return 0;
}