算法-图论

发表于 2022-06-21 更新于 2023-01-21

包括了图论的一些常用算法的定义、说明、代码实现。

图的存储

设有向图 $G=(V,E)$ ， $V$ 为点集， $E$ 为边集， $(x, y)$ 表示从 $x$ 到 $y$ 的有向边，其边权为 $w(x, y)$ 。记 $n = |V|$ ， $m = |E|$ 。

对于图，一般使用邻接矩阵或邻接表来进行存储。前者存储稠密图，后者存储稀疏图。所谓稠密图，指的是 $m$ 近似于 $n^2$ 。

记邻接矩阵 $A$ ，其定义可以表示如下：

A[i, j] = \begin{cases} 0 & & i=j \\ w(i, j) & & (i, j) \in E \\ +\infty & & (i, j) \notin E \end{cases}

其空间复杂度为 $O(n^2)$ 。

稀疏图表示 $m$ 近似于 $kn$ ，其中 $k$ 为常数。稀疏图使用邻接表存储。

邻接表可以看成带有索引数组的多个数据链表的结构集合。数据被分为若干类，每一类的数据构成一个链表，每一类有一个代表数据，作为表头。所有表头构成一个表头数组，作为一个可以随机访问的索引。

在一个具有 $n$ 个点， $m$ 条边的有向图结构中，我们可以记类别为该边的起点编号。这样 $m$ 条边就分成 $n$ 类，记第 $x$ 类为“从 $x$ 出发的所有边”，通过表头head[x]，可以定位从 $x$ 出发的所有边。

使用如下数据构建邻接表：

head[x]表示由节点x连接的边的链表的头节点
edge[i]表示边i的目标节点
weight[i]表示边i的权重
ne[i]表示对应链表中的下一条边的编号

在这种表示方法下，向图中加入一条边可以写为：

int tot;                                    // 边的总数

void add(int u, int v, int w)
{
    edge[++tot] = v, weight[tot] = w;       // 记录边的数据
    ne[tot] = head[x], head[x] = tot;       // 更新链表，头插节点
}

遍历从一个点出发的所有边可以写为：

for (int i = head[u]; ~i; i = ne[i])        // 假定链表尾的ne[i] = -1 
{
    int v = edge[i], w = weight[i];
    /*
        do some stuff
    */
}

无向图的存图方式与有向图完全相同。在邻接数组中，有 $A[i, j] = A[j, i]$ 。在邻接表中，可通过添加正反两条边的方式存储无向图。此时，通过置tot初值为1，我们可以获得编号为2和3、4和5……等的正反边。注意到此时，edge[x]与edge[x ^ 1]分别表示正反边，且正向边的编号一定为偶数。

单源最短路径（Single Source Shortest Path）

给定一张有向图 $G=(V, E)$ ， $V$ 为点集， $E$ 为边集， $n = |V|$ ， $m = |E|$ ，节点以 $[1, \ n]$ 编号， $(x, y, z)$ 描述一条从 $x$ 出发，到达 $y$ ，权重为 $z$ 的有向边。求 $dist[n]$ 数组，使得 $dist[i]$ 表示从起点 $1$ 到节点 $i$ 的最短路径的长度。

Dijkstra算法

算法流程如下：

初始化 $dist[1]$ 为 $0$ ，其余为无穷大
找出未被标记的， $dist[x]$ 最小的节点 $x$ ，标记节点 $x$
扫描 $x$ 的所有出边 $(x, y, z)$ ，若 $dist[y] > dist[x] + z$ ，则更新 $dist[y]$ 为 $dist[x] + z$ 。
重复 2 ~ 3步骤，直到所有节点都被标记

Dijkstra算法基于贪心思想，适用于无负权边的图。不存在负权边时，全局最小值 $dist[x]$ 不可能再被更新，故其即为 $1$ 到 $x$ 的最短路。不断选择全局最小值并更新，即可计算所有点的最短路长度。

朴素

在稠密图下，使用邻接矩阵存图，寻找 $dist[x]$ 的方式是：直接遍历 $dist$ 数组。同时，每一次遍历领边需要检查所有点，易得时间复杂度为 $O(n^2)$ 。

int a[N][N];
int dist[N];
bool st[N];

void dijkstra()
{
    memset(dist, 0x3f, sizeof(dist));
    memset(st, 0, sizeof(0));
    dist[1] = 0;
    for (int i = 1; i < n; ++i) // 不需要考虑点 1，循环 n - 1 次。
    {
        int x = 1;
        for (int j = 1; j <= n; ++j)
            if (!st[j] && dist[j] < dist[x])
                x = j;
        st[x] = true;
        for (int y = 1; y <= n; ++y)
            dist[y] = min(dist[y], dist[x] + a[x][y]);
    }
}

堆优化

容易想到，使用堆维护全局最小值。

using PII = pair<int, int>;

void dijkstra()
{
    priority_queue<PII, vector<PII>, greater<PII>> pq;
    memset(dist, 0x3f, sizeof(dist));
    memset(st, 0x3f, sizeof(dist));
    dist[1] = 0;
    pq.push({0, 1});

    while (pq.size())
    {
        int d, x;
        tie(d, x) = pq.top();
        pq.pop();
        if (st[x] || d > dist[x])
            continue;
        st[x] = true;
        for (int i = head[x]; ~i; i = ne[i])     // 假定链表尾的ne[i] = -1
        {
            int y = edge[i], w = weight[i];
            if (dist[y] > dist[x] + w)
            {
                dist[y] = dist[x] + w;
                pq.push({dist[y], y});
            }
        }
    }
}

考虑到更新每个边时都有可能入堆，故实际复杂度为 $O(mlogm)$ ，考虑到 $m < n^2$ ，即复杂度为 $O(mlogn)$

Bellman-Ford算法和SPFA算法

Bellman-Ford基于迭代思想。若所有边都满足 $dist[y] \le dist[x] + z$ ，则 $dist$ 即为最短路数组。

扫描所有边 $(x, y, z)$ ，若 $dist[y] > dist[x] + z$ ，则更新 $dist[y]$ 。
重复上述步骤，直到没有更新发生。

Bellman-Ford算法的时间复杂度为 $O(nm)$ 。

SPFA又称为“队列优化的Bellman-Ford算法”，SPFA算法流程如下：

建立队列，初始队列中只含有节点1。
取出队头节点 $x$ ，扫描所有出边 $(x, y, z)$ ，若 $dist[y] > dist[x] + z$ ，则更新 $dist[y]$ ，若 $z$ 不在队中，将 $z$ 入队。
重复2，直到队列为空

SPFA算法基于一种朴素的思想：只有更新了 $x$ 之后，其对应的出边 $y$ 才有可能被更新。SPFA避免了对不需要扩展的节点的冗余扫描，在随机图上时间复杂度为 $O(km)$ ，在特殊构造的图上可能退化为 $O(nm)$ 。

void spfa()
{
    memset(dist, 0x3f, sizeof(dist));
    queue<int> q;
    dist[1] = 0, st[1] = true;      // st数组在SPFA中表示为：
    q.push(1);                      // 点是否在队列中

    while (q.size())
    {
        int x = q.front();
        p.pop();
        st[x] = false;
        for (int i = head[x]; ~i; i = ne[i])
        {
            int y = edge[i], w = edge[i];
            if (dist[y] > dist[x] + w)
            {
                dist[y] = dist[x] + w;
                if (!st[y])
                {
                    q.push(y);
                    st[y] = true;
                }
            }
        }
    }
}

Bellman-Ford算法与SPFA算法适用于无负环图。

任意两点间最短路

一般使用Floyd算法在 $O(n^3)$ 的时间内求解任意两点间最短路。

Floyd算法基于DP。记 $D[k, i, j]$ 表示经过若干个编号不超过 $k$ 的节点，从 $i$ 到 $j$ 的最短路。该问题可划分为两个子问题：经过编号不超过 $k-1$ 的点从 $i$ 到 $j$ ，或从 $i$ 先到 $k$ 再到 $j$ 。故有：

D[k, i, j] = min(D[k - 1, i, j], D[k - 1, i, k] + D[k - 1, k, j])

$k$ 表示阶段，所以必须置于最外层循环中。 $k$ 这一维在这一情况下可以省略。

D[i, j] = min(D[i, j], D[i, k] + D[k, j])

$D$ 矩阵的初始值与邻接矩阵相同。

void floyd()
{
    for (int k = 1; k <= n; ++i)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

类似地，可以计算传递闭包

void floyd()
{ // bool d[N][N];
    for (int k = 1; k <= n; ++i)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                d[i][j] |= d[i][k] & d[k][j];
}

最小生成树（Minimum Spanning Tree）

给定一张边带权的无向图 $G = (V, E)$ ， $n=|V|$ ， $m=|E|$ 。由 $V$ 中全部顶点和 $E$ 中 $n-1$ 条边构成的无向联通子图被称为 $G$ 的一棵生成树。边权值之和最小的生成树被称为无向图 $G$ 的最小生成树。

定理
任意一棵最小生成树一定包含无向图中权值最小的边。证明略。

推论
给定一张无向图 $G = (V, E)$ ， $n=|V|$ ， $m=|E|$ 。从 $E$ 中选出 $k<n-1$ 条边构成 $G$ 的一个生成森林，若在从剩余的 $m-k$ 条边中选 $n-k-1$ 条添加到生成森林中，使之成为生成树，并且选出的边的权值之和最小。则该生成树一定包含这 $m-k$ 条边中连接森岭的两个不连通节点的权值最小的边。

Kruskal算法

基于上述推论可以得出Kruskal算法：维护最小生成森林，从剩余边中挑出一条权值最小的连接两个不连通树的边，并加入到最小生成森林中，直到它变成树。

建立并查集，每个点各自构成一个集合
把所有边按照权值大小从小到大排序
依次扫描每一条边，如果 $(x,y)$ 属于同意集合，则忽略
否则，合并 $x$ ， $y$ 所在的集合，并把 $z$ 累加到答案中
所有边扫描完成后，第4步中的边构成最小生成树

时间复杂度为 $O(mlogn)$ 。

struct Edge{ int x, y, z; } edges[M];
int p[N];
int find(int x)
{
    if (x == p[x])
        return x;
    return p[x] = find(x);
}

int kruskal()
{
    int sum = 0;
    sort(edge + 1, edge + 1 + m, [](Edge a, Edge b) -> bool
        {return a.z < b.z});
    for (int i = 1; i <= n; ++i)
        p[i] = i;
    for (int i = 1; i <= m; ++i)
    {
        int a = find(edge[i].x);
        int b = find(edge[i].y);
        if (a == b)
            continue;
        p[a] = b;
        res += edge[i].z;
    }
    return res;
}

Prim算法

Prim算法总是维护最小生成树的一部分。

在任意时刻，设已经确定属于最小生成树的节点集合为 $T$ ，剩余节点集合为 $S$ ，Prim算法找到 $min_{x\in S, y\in T}\{z\}$ ，然后把点 $x$ 从 $S$ 移到 $T$ ，并累加边权 $z$ 。

Prim算法的时间复杂度为 $O(n^2)$ ，因此常用于邻接矩阵存储的稠密图。

int grid[N][N], dist[N];
bool st[N];     // 1表示处于S集合

int prim()
{
    int res = 0;
    memset(dist, 0x3f, sizeof(dist));
    memset(st, 0, sizeof(st));
    dist[1] = 0, st[1] = 1;
    for (int i = 2; i <= n; ++i)
    {
        int x = 1;
        for (int j = 2; j <= n; ++j)
            if (!st[j] && dist[j] < dist[x])
                x = j;
        st[x] = true;
        for (int y = 1; y <= n; ++y)
            if (!st[y])
                dist[y] = min(dist[y], grid[x][y]);
    }
}

树的直径

树中最远的两个节点之间的距离被称为树的直径，连接这两点的路径被称为树的最长链。

树的直径一般有两种求法

树形DP

不妨设 1 号节点为根，图就可以看作有根树。设 $D[x]$ 表示从节点 $x$ 出发走向以 $x$ 为根的子树，能够到达的节点的最远的距离。设 $x$ 的子节点为 $y_1,y_2,···,y_t$ , $edge(x, y)$ 表示边权，显然有

D[x] = max_{1\le i\le t}\{D[y_i] + edge(x, y_i)\}

设经过节点 $x$ 的直径长度为 $F[x]$ ，整棵树的直径就是 $max_{1\le x\le n}\{F[x]\}$ 。

显然，根据此定义， $x$ 的最长链有可能经过父节点。但是此时父节点的最长链的枚举一定包括了此链，所以求 $F[x]$ 时只需在子树上求解即可。

$F[x]$ 可以由四部分构成：从 $y_i$ 到 $y_i$ 子树中最远距离，边 $(x,y_i)$ ，边 $(x,y_j)$ ，从 $y_j$ 到 $y_j$ 子树中最远距离。

在求解过程中， $D[x]$ 恰好保存枚举过的 $D[y_i] + edge(x, y_i)$ 的最大值，利用此即可避免使用二重循环。也就是说，我们首先利用 $D[x] + D[y_j] + edge(x, y_j)$ 更新 $F[x]$ ，再用 $D[y_j] + edge(x, y_j)$ 更新 $D[x]$ 。

void dp(int x)
{
    st[x] = 1;
    for (int i = head[x]; ~i; i = ne[i])
    {
        int y = edge[i];
        if (st[y])  // y 不是子节点
            continue;
        dp(y);
        res = max(res, d[x] + d[y] + weight[i]);
        d[x] = max(d[x], d[y] + weight[i]);
    }
}

两次bfs

这种方法可以算出树上的具体节点，但是无法适用于带负权边的树

从任意一个节点出发，遍历树，求出与出发距离最远的节点，记为 $p$
从 $p$ 出发，再进行一次遍历，求出与 $p$ 距离最远的节点，记为 $q$

从 $p$ 到 $q$ 的路径就是树的直径。

在第二步中，可以记录下来每个点第一次被访问时的前驱节点，最后从 $q$ 递归到 $p$ ，即可得到直径的具体方案。

最近公共祖先（LCA）

给定一棵有根树，若节点 $z$ 既是节点 $x$ 的祖先，也是节点 $y$ 的祖先，则称 $z$ 是 $x, y$ 的公共祖先。在 $x,y$ 的所有公共祖先中，深度最大的一个称为 $x,y$ 的最近公共祖先。

求解 $LCA$ 的算法有三种：

向上标记法

从 $x$ 向上走到根节点，并标记所有经过的节点

从 $y$ 向上走到根节点，当第一次遇到已标记的节点时，就找到了 $LCA(x, y)$

树上倍增法

设 $F[x, k]$ 表示 $x$ 的 $2^k$ 辈祖先，若不存在则为 $0$ 。 $F[x, 0]$ 就是 $x$ 的父节点。除此之外，显然有 $\forall k \in [1, logn],\ F[x, k] = F[F[x, k-1], k-1]$ 。

我们可以对树进行广度优先遍历，按照层次顺序，在节点入队之前，计算在 $F$ 数组中对应的值。这是预处理部分，时间复杂度为 $O(nlogn)$ 。

基于 $F$ 数组计算 $LCA(x, y)$ 如下：

设 $d[x]$ 表示 $x$ 的深度。不妨设 $d[x] \ge d[y]$ （否则可交换 $x,y$ ）。
用二进制拆分，把 $x$ 上调到与 $y$ 同一深度。
若此时 $x=y$ ，说明 $LCA(x,y)=y$
用二进制拆分思想，把 $x,y$ 同时向上调整，并且保持深度一致且二者不相会。
此时 $F[x,0]$ 就是 $LCA$ 。

void build()
{
    queue<int> q;
    q.push(root);
    depth[root] = 1;
    while (q.size())
    {
        int u = q.front();
        q.pop();
        for (int i = head[u]; ~i; i = ne[i])
        {
            int v = edge[i];
            if (depth[v])
                continue;
            depth[v] = depth[u] + 1;
            f[v][0] = u;
            for (int j = 1; j < K; ++j)
                f[v][j] = f[f[v][j - 1]][j - 1];
            q.push(v);
        }
    }
}

int lca(int x, int y)
{
    if (depth[x] > depth[y])
        swap(x, y);
    for (int i = K - 1; i >= 0; --i)
        if (depth[f[y][i]] >= depth[x])
            y = f[y][i];
    if (x == y)
        return x;
    for (int i = K - 1; i >= 0; --i)
        if (f[x][i] != f[y][i] && f[x][i] != 0)
            x = f[x][i], y = f[y][i];
    return f[x][0];
}

LCA的Tarjan算法

在深度优先遍历的任意时刻，树中节点分为三类：

已经访问完毕并且回溯的节点。在这些节点上标记整数2。
已经开始递归，但是尚未回溯的节点，这些节点就是正在访问的节点 $x$ 和 $x$ 的祖先。在这些节点上标记1。
尚未访问的节点，这些节点没有标记。

对于正在访问的节点 $x$ ，若 $y$ 是已经访问完毕并且回溯的节点，则 $LCA(x, y)$ 等于从 $y$ 向上走到根，第一个遇到的标记为 1 的节点。

可以利用并查集进行优化，当一个节点获得整数 2 时，把它所在的集合合并到它的父节点所在的集合中（合并时它的父节点一定为 1，且单独构成一个集合）。

在这种优化下，只需查询 $y$ 所在集合的代表元素，就等价于从 $y$ 一直向上走到标记1的节点，即 $LCA(x,y)$ 。

int p[N], dist[N], st[N], ans[M];
vector<int> queries[N], queries_id[N];

void add(int a, int b, int w)
{
    edge[++tot] = b, weight[tot] = w;
    ne[tot] = head[a], head[a] = tot;
}

void add_query(int a, int b, int id)
{
    queries[a].push_back(b), queries_id[a].push_back(id);
    queries[b].push_back(a), queries_id[b].push_back(id);
}

int find(int x)
{
    if (p[x] == x)
        return x;
    return p[x] = find(p[x]);
}

void tarjan(int u)
{
    st[u] = 1;
    for (int i = head[u]; ~i; i = ne[i])
    {
        int v = edge[i], w = weight[i];
        if (st[v])
            continue;
        dist[v] = dist[u] + w;
        tarjan(v);
        p[v] = u;
    }
    for (int i = 0; i < queries[u].size(); ++i)
    {
        int v = queries[u][i], id = queries_id[u][i];
        if (st[v] == 2)
        {
            int lca = find(v);
            ans[id] = min(ans[id], dist[u] + dist[v] - 2 * dist[lca]);
        }
    }
    st[u] = 2;
}

基环树

在树上任意添加一条边，会形成一个环，我们称之为“基环树”。求解基环树问题的一般方法是，找出图中的唯一一个环，将其作为广义的根节点，把环之外的部分按照树来处理。

负环与差分约束

负环

判断负环有两种方式：

Bellman-Ford判定负环
若经过 n 轮迭代，算法仍未结束（仍有能产生更新的边），则图中存在负环
SPFA判定负环
设 cnt[x] 表示从 1 到 x 的最短路径包含的边数，cnt[1] = 0，当更新dist数组时同样更新cnt，若存在cnt[y] ≥ n，则有负环。

差分约束

差分约束是一组形如 $X_i - X_j \le c_k$ 的不等式，我们要解决的问题是：求一组 $X_i=a_i$ 使得所有约束条件得到满足。

考虑到差分约束类似于三角不等式，对每个约束条件在图中作一条边，增加零号节点并使 $X_i-X_{0} \le 0$ ，从零号节点开始求最短路，所得dist数组即为一个解。若存在负环则无解。

Tarjan算法与有向图连通性

给定有向图 $G=(V,E)$ ，若存在 $r \in V$ ，满足从 $r$ 出发能够到达 $V$ 中所有的点，则称 $G$ 是一个“流图”（Flow Graph），记为 $(G,r)$ ，其中 $r$ 称为流图的流点。

在一个流图 $(G,r)$ 上从 $r$ 出发进行深度优先遍历，每个点只访问一次。所有发生递归的边 $(x,y)$ （换而言之，从 $x$ 到 $y$ 是对 $y$ 的第一次访问）构成一棵以 $r$ 为根的树，我们把它称为流图 $（G,r）$ 的搜索树。

同时，在深度优先遍历的过程中，按照每一个节点第一次被访问的时间顺序，一次给予流图中 $N$ 个节点 $1\sim N$ 的整数标记，该标记被称为时间戳，记为 $dfn[x]$ 。

流图中的每一条有向边 $(x,y)$ 必定是以下四种之一：

树枝边，指搜索树中的边，即 $x$ 是 $y$ 的父节点。
前向边，指搜索树中 $x$ 是 $y$ 的祖先节点。
后向边，指搜索树中 $y$ 是 $x$ 的祖先节点。
横叉边，指除了以上三种情况的边，它一定满足 $dfn[y] < dfn[x]$ 。

有向图的强连通分量（Strongly Connected Component, SCC）

给定一张有向图。若对于图中任意两个节点 $x,y$ ，既存在从 $x$ 到 $y$ 的路径，也存在从 $y$ 到 $x$ 的路径，则称该有向图是“强连通图”。有向图的极大强连通子图被称为“强连通分量”，简记为SCC。

Tarjan算法的思路是尽量找到能与某个节点构成环的所有节点。

Tarjan算法在深度优先遍历的同时维护了一个栈。当访问到节点 $x$ 时，栈中需要保存以下两类节点：

搜索树上 $x$ 的祖先节点，记为集合 $anc(x)$ 。
设 $y \in anc(x)$ 。若存在后向边 $(x,y)$ ，则 $(x,y)$ 与 $y$ 到 $x$ 的路径一起形成环。
已经访问过，并且存在一条路径到达 $anc(x)$ 的节点。
设 $z$ 是一个这样的节点，从 $z$ 出发存在一条路径到达 $y\in anc(x)$ 。若存在横叉边 $(x,z)$ ，则 $(x,z)$ 、 $z$ 到 $y$ 的路径、 $y$ 到 $x$ 的路径形成一个环。

综上所述，栈中的节点就是能够与从 $x$ 出发的后向边或横叉边形成环的节点。

追溯值
设 $subtree(x)$ 表示流图的搜索树中以 $x$ 为根的子树。 $x$ 的追溯值 $low[x]$ 定义为满足以下条件的节点的最小时间戳。

存在栈中。
存在一条从 $subtree(x)$ 出发的有向边，以该点为终点。

根据定义，Tarjan算法按照以下步骤计算“追溯值”。

当节点第一次被访问时， $x$ 入栈，初始化 $low[x]=dfn[x]$ 。
扫描从 $x$ $x$ 出发的每条边 $(x,y)$ $(x, y)$ 。
1. 若 $y$ 没被访问过，则说明 $(x,y)$ 是树枝边，递归访问 $y$ ，从 $y$ 回溯之后，令 $low[x]=min(low[x],low[y])$ 。
2. 若 $y$ 被访问过且在栈中，则令 $low[x]=min(low[x],dfn[y])$ 。
从 $x$ 回溯之前，判断是否有 $low[x]=dfn[x]$ 。若成立，则不断从栈中弹出节点，直至 $x$ 出栈。

强连通分量判定法则
在追溯值的计算中，若从 $x$ 回溯前，有 $low[x]=dfn[x]$ ，则栈中从 $x$ 到栈顶的所有节点构成一个强连通分量。

stack<int> stk;
bool ins[N];    // in stack
int c[N];       // identifier of SCC
int dfn[N], low[N], num, cnt;   
vector<int> scc[N];  

void tarjan(int u)
{
    dfn[u] = low[u] = ++num;
    stk.push(u), ins[u] = true;
    for (int i = head[u]; ~i; i = ne[i])
    {
        int v = edge[i];
        if (!dfn[v])
        {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (ins[v])
            low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u])
    {
        cnt++;
        int x;
        do {
            x = stk.top(), ins[x] = false;
            stk.pop();
            c[x] = cnt, scc[cnt].push_back(x);
        } while (x != u);
    }
}

可以使用缩点的方式建立新的有向无环图

void add_c(int x, int y)
{
    vc[++tc] = y, nc[tc] = hc[x], hc[x] = tc;
}

// 在 main 函数中
for (int x = 1; x <= n; ++x)
    for (int i = head[x]; ~i; i = ne[i])
    {
        int y = edge[i];
        if (c[x] == c[y])
            continue;
        add_c(c[x], c[y]);
    }

2-SAT

有 $N$ 个变量，每个变量只有两种可能的取值。再给定 $M$ 个条件，每个条件都是对两个变量的取值限制。求是否存在对 $N$ 个变量的合法取值，使得 $M$ 个条件均满足，这就是 2-SAT 问题。

该问题判定方法如下：

建立 $2N$ 个节点的有向图，每个变量 $A_i$ 对应 $2$ 个节点，一般设为 $i$ 和 $i+N$ 。
考虑每个条件，形如“若变量 $A_i$ 赋值为 $A_{i,p}$ ，则变量 $A_j$ 赋值为 $A_{j,q}$ ”，其中 $p,q\in \{0, 1\}$ 。
用 Tarjan 算法求出有向图中所有的强连通分量。
若存在 $i\in [1,N]$ ，满足 $i$ 和 $i+N$ 属于同一个强连通分量，则存在矛盾。否则可以构造出一个可行解。

注意第二点需要考虑等价的逆否命题。

欧拉路问题

给定一张无向图，若存在一条从节点 $S$ 到节点 $T$ 的路径，恰好不重不漏地经过每条边一次（可以重复经过顶点），则称该路径为 $S$ 到 $T$ 的欧拉路。

特别的，若回到起点 $S$ ，则称该路径为欧拉回路。存在欧拉回路的无向图被称为欧拉图。

欧拉图的判定：一张图为无向图，当且仅当无向图连通，并且每个点的度数都是偶数。

欧拉回路的判定：一张图中存在欧拉回路，当且仅当无向图连通，并且图中恰好有两个点的度数为奇数，其他节点的度数都是偶数。这样个点就是欧拉路的起点和终点。

求欧拉回路的一种流程为：

void dfs(int x)
    对于从x出发的每条边(x,y)
        如果该边没有访问过
            把这条边标记为已访问
            dfs(y)
            把y入栈

主函数中：
    dfs(1)
    倒序输出栈中所有的节点

一种优化方法是，对于一个访问过的边，在邻接表中令表头直接指向下一条边，这就避免了重复访问边。

因为欧拉回路DFS的层数非常大，为了避免系统栈溢出，使用栈模拟递归。

int ans[M], t = 0;
bool st[M]; // 标记边而非顶点
void euler()
{
    stack<int> stk;
    stk.push(1);
    while (stk.size())
    {
        int u = stk.top();
        int i = head[u];
        while (~i && st[i])
            i = ne[i];
        if (~i)
        {
            stk.push(edge[i]);
            st[i] = st[i ^ 1] = true; // 标记双向边
            head[x] = ne[i];
        }
        else // 遍历完该点所有边
        {
            stk.pop();
            ans[++t] = u;
        }
    }
}

二分图

如果一张无向图的 $N$ 个节点（ $N \ge 2$ ）可以分成 $A,B$ 两个非空集合，其中 $A \cap B = \empty$ ，并且在同一集合内的点之间都没有边相连，那么称这张图为一张二分图， $A$ ， $B$ 分别称为二分图的左部和右部。

判定

定理：一张图是二分图，当且仅当图中不存在长度为奇数的环。

用染色法进行二分图的判定，大致思想：尝试用两种颜色标记图中的节点，当一个节点被标记后，它的所有相邻节点被标记与它相反的颜色，若标记过程产生冲突，则图中存在奇环。

最大匹配

“任意两条边都没有公共端点”的边的集合被称为图的一组匹配。在二分图中，包含边数最多的一组匹配被称为二分图的最大匹配。

如果二分图中存在一条连接两个非匹配点的路径 path，使得非匹配边与匹配边在path上交替出现，那么称path是匹配 $S$ 的增广路。

二分图的一组匹配是最大匹配，当且仅当图中不存在 $S$ 的增广路。

匈牙利算法用来计算二分图最大匹配，它的主要过程为：

设 $S=\empty$ ，即所有的边都是非匹配边
寻找增广路path，把路径上所有边的匹配状态取反，得到一个更大的匹配 $S'$
重复第二步，直到图中不存在增广路

该算法的关键在于如何找到增广路。匈牙利算法尝试给每一个左部节点 $x$ 寻找一个匹配的右部节点 $y$ 。右部点 $y$ 能与左部点 $x$ 匹配，需要满足以下两个条件之一。

$y$ 本身是非匹配点
$y$ 已经与左部点 $x'$ 匹配，但从 $x'$ 出发能找到另一个右部点 $y'$ 与之匹配，此时路径 $x\sim y\sim y'\sim x'$ 为一条增广路

时间复杂度为 $O(nm)$

bool dfs(int x)
{
    for (int i = head[x]; ~i; i = ne[i])
    {
        int y = edge[i];
        if (!visit[y])
        {
            visit[y] = true;
            if (!match[y] || dfs(match[y]))
            {
                match[y] = x;
                return true;
            }
        }
    }
    return false;
}

for (int i = 1; i <= n; ++i)
{
    memset(visit, 0, sizeof(visit));
    if (dfs(i))
        ans++;
}

带权匹配

给定一张二分图，二分图的每一条边都带有一个权值。求出该二分图的一组最大匹配，使得匹配边的权值总和最大。这个问题被称为二分图的带权最大匹配，也称二分图的最优匹配。

交错树
在匈牙利算法中，如果从某个左部节点出发寻找匹配失败，那么在 DFS 的过程中，所有访问过的节点，以及为了访问这些节点而经过的边，共同构成一棵树。这棵树的根是一个左部节点，所有叶子节点也都是左部节点，奇数层边是非匹配边，偶数层边是匹配边，因此，这棵树被称为交错树。

顶标
全称“顶点标记值”。在二分图中，给第 $i$ 个左部节点一个整数值 $A_i$ ，给第 $j$ 个右部节点一个整数值 $B_j$ 。同时，必须满足 $\forall i,j,A_i+B_j\ge w(i,j)$ ，其中 $w(i,j)$ 表示第 $i$ 个左部点与第 $j$ 个右部点之间的边权（没有边时设为负无穷）。这些整数值 $A_i,B_j$ 称为节点的顶标。

相等子图
二分图中所有节点和满足 $A_i+B_j=w(i,j)$ 的边构成的子图，称为二分图的相等子图。

若相等子图中存在完备匹配，则这个完备匹配就是二分图的带权最大匹配。

求解最大带权匹配

KM算法的基本思想是，在满足 $\forall i,j, A_i+B_j \ge w(i,j)$ 的前提下，先给每个节点赋值 $A_i=max_{1\le j \le n}\{w(i,j)\}，B_j=0$ ，然后不断扩大相等子图的规模。

对于一个相等子图，如果最大匹配不完备，说明一定有一个左部节点匹配失败。记匹配这个节点时访问到的路径为一棵交错树 $T$ 。此时降低 $T$ 中的 $A_i$ 的值∇，同时增加所有 $T$ 中的 $B_j$ 值 ∇，则原匹配边仍在相等子图中，而左部点沿着非匹配边访问不在子图中的 $B_j$ 时，由于 $A_i+B_j$ 减少，所以可能新增加点到子图中。

实际上，我们在所有 $i\in T,j \notin T$ 的边中，找到最小 $A_i+B_j-w(i,j)$ 作为 ∇ 值，这样对应的左部点就能增加一个匹配的右部点，使得相等子图得到扩大。

不断重复以上过程，直到每一个左部点都匹配成功，就得到了相等子图的完备匹配，即原图的最大带权匹配。具体实现时，可以在DFS中维护一个数组记录可能更新 ∇ 的值。时间复杂度为 $O(N^2M)$ 。

int w[N][N];
int la[N], lb[N];  // 节点顶标
bool va[N], vb[N]; // 访问标记，是否在交错树中
int match[N];
int n, nabla, upd[N];

bool dfs(int x)
{
    va[x] = 1; // x 本身必处在交错树中
    for (int y = 1; y <= n; y++)
        if (!vb[y])
        {
            if (la[x] + lb[y] - w[x][y] == 0) // 相等子图
            {
                vb[y] = 1;
                if (!match[y] || dfs(match[y]))
                {
                    match[y] = x;
                    return true;
                }
            }
            else
                upd[y] = min(upd[y], la[x] + lb[y] - w[x][y]);
        }
    return false;
}

int KM()
{
    for (int i = 1; i <= n; i++)
    {
        la[i] = -0x3f3f3f3f;
        lb[i] = 0;
        for (int j = 1; j <= n; j++)
            la[i] = max(la[i], w[i][j]);
    }
    for (int i = 1; i <= n; i++)
    {
        while (true) // 直到左部节点找到匹配边
        {
            memset(va, 0, sizeof(va));
            memset(vb, 0, sizeof(vb));
            memset(upd, 0x3f, sizeof(upd));
            if (dfs(i))
                break;
            nabla = 0x3f3f3f3f;
            for (int j = 1; i <= n; j++)
                if (!vb[j])
                    nabla = min(nabla, upd[j]);
            for (int j = 1; j <= n; j++)
            {
                if (va[j])
                    la[j] -= nabla;
                if (vb[j])
                    lb[j] += nabla;
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans += w[match[i]][i];
    return ans;
}

优化算法

可以进一步把算法优化到 $O(N^3)$ 。考虑到已经遍历过的交错树不需要再次遍历，只需要从新加入的最小的边开始搜索即可。我们还需要 $last$ 数组来记录每个右部节点 $j$ 在交错树中的上一个右部节点，沿 $last$ 倒推更新增广路。

bool dfs(int x, int p)
{
    va[x] = 1;
    for (int y = 1; y <= n; y++)
        if (!vb[y])
        {
            if (la[x] + lb[y] - w[x][y] == 0)
            {
                vb[y] = 1;
                last[y] = p;
                if (!match[y] || dfs(match[y], y)) 
                {
                    match[y] = x;
                    return true;
                }
            }
            else if (upd[y] > la[x] + lb[y] - w[x][y])
            {
                upd[y] = la[x] + lb[y] - w[x][y];
                last[y] = p;
            }
        }
    return false;
}

int KM()
{
    for (int i = 1; i <= n; i++)
    {
        la[i] = -0x3f3f3f3f;
        lb[i] = 0;
        for (int j = 1; j <= n; j++)
            la[i] = max(la[i], w[i][j]);
    }
    for (int i = 1; i <= n; i++)
    {
        memset(va, 0, sizeof(va));
        memset(vb, 0, sizeof(vb));
        memset(last, 0, sizeof(last));
        memset(upd, 0x3f, sizeof(upd));
        // 从右部点 st 匹配的左部点开始 dfs，一开始假设有一条匹配
        int st = 0, match[0] = i;
        while (match[st])
        {
            int nabla = 0x3f3f3f3f;
            if (dfs(match[st]), st)
                break;
            for (int j = 1; j <= n; j++)
            {
                if (!vb[j] && upd[j] < nabla)
                {
                    nabla = upd[j];
                    st = j; // 下次从最小边开始 dfs
                }
            }
            for (int j = 1; j <= n; j++)
            {
                if (va[j])
                    la[j] -= nabla;
                if (vb[j])
                    lb[j] += nabla;
                else
                    upd[j] -= nabla;
            }
            vb[st] = 1;
        }
        while (st)
        {
            match[st] = match[last[st]];
            st = last[st];
        }
        int ans = 0;
        for (int i = 1; i <= n; i++)
            ans += w[match[i]][i];
        return ans;
    }
}

最小点覆盖

给定一张二分图，求出一个最小的点集 $S$ ，使得图中任意一条边都有至少一个端点属于 $S$ ，这个问题被称为二分图的 最小点覆盖（vertex cover），简称最小覆盖。

二分图最小点覆盖包含的点数等于二分图最大匹配包含的边数。

最大独立集

给定一张无向图 $G=(V,E)$ ，满足下列条件的点集 $S$ 被称为图的独立集。

$S\in V$
$\forall x,y \in S，(x,y)\notin E$

图的独立集就是任意两点之间都没有边相连的点集。

“任意两点之间都有一条边相连”的子图被称为无向图的“团”，点数最多的团被称为最大团。

定理

无向图 $G$ 的最大团等于其补图 $G'$ 的最大独立集。 $G'=(V,E')$ 被称为 $G=(V,E)$ 的补图，其中 $E'=\{(x,y)\notin E\}$ 。
设 $G$ 是一个有 $n$ 个节点的二分图， $G$ 的最大独立集的大小等于 $n$ 减去最大匹配数。这是因为去掉二分图的最小点覆盖，剩余部分自然组成最大独立集。

有向无环图的最小路径点覆盖

给定一张有向无环图，要求用尽量少的不相交的简单路径，覆盖有向无环图的所有顶点。这个问题被称为有向无环图的最小路径点覆盖。

设原来的有向无环图为 $G=(V,E), n = |V|$ 。把 $G$ 中的每个点 $x$ 拆成编号为 $x$ 和 $x+n$ 的两个点，建立一张新的二分图， $1\sim n$ 作为二分图左部点， $n+1\sim 2n$ 作为二分图右部点，对于原图的每条有向边 $(x,y)$ ，在二分图的左部点 $x$ 与右部点 $y+n$ 之间连边，最终得到的二分图称为 $G$ 的拆点二分图，记为 $G_2$ 。

有向无环图 $G$ 的最小路径点覆盖包含的路径条数，等于 $n$ 减去拆点二分图 $G_2$ 的最大匹配数。

网络流

流网络

一个流网络 $G=(V,E)$ 是一张有向图，图中每条有向边 $(x,y) \in E$ 都有一个给定的权值 $c(x,y)$ ，称为边的容量。图中还有两个指定的特殊节点 $S\in V$ 和 $T\in V$ ，分别称为源点和汇点。

设 $f(x,y)$ 是定义在节点二元组（ $x\in V$ ， $y\in V$ ）上的实数函数，且满足：

容量限制： $f(x,y)\le c(x,y)$
$f(x,y)=-f(y,x)$
流量限制： $\forall x \neq S，x\neq T$ ， $\sum_{(u,x)\in E}f(u,x)=\sum_{(x,v)\in E}f(x,v)$

$f$ 称为网络的流函数，对于 $(x,y)\in E$ ， $f(x,y)$ 称为边的流量， $c(x,y)-f(x,y)$ 称为边的剩余容量。

从源点 $S$ 流向其他店的流量，大小为 $|f|=\sum_{(S,v)\in E}f(S,v)$ ，称为整个网络的流量。

最大流

使得整个网络流量最大的流函数被称为网络的最大流。

残量网络

对于一个流量图的网络流 $f$ ，记其残差网络为 $G_f$ ，两者一一对应。

$G_f=(V_f, E_f)$ ，其中 $V_f=V，E_f = E \cup E'$ 。残差网络中各个边对应容量定义如下：

c'(u,v)= \begin{cases} c(u,v)-f(u,v) & (u,v)\in E \\ f(u,v) & (u,v) \notin E \end{cases}

反向边容量等于原图正向边流量，正向边容量等于原图边容量减去差值。可以证明 $|f+f'|=|f|+|f'|$ 。

Edmonds-Karp 增广路算法

若残量网络上一条从源点 $S$ 到汇点 $T$ 的路径中各条边的容量都大于 0，则称这条路径为一条增广路。显然，可以让一股流沿着增广路从 $S$ 流到 $T$ ，使网络的流量增大。EK算法不断用BFS寻找增广路，直到网络上不存在增广路为止。

在每轮寻找增广路的过程中，EK算法只考虑图中所有 $f(x,y) < c(x,y)$ 的边，用 BFS 找到一条从 S 到 T 包含边数最少（长度最短）的路径，同时计算出路径上各边的剩余容量的最小值 $min(f)$ ，则网络的流量就可以增加 $min(f)$ 。

int n, m, s, t;
int head[N], ne[M], edge[M], weight[M], tot = 1;
int d[N], pre[N];
bool vis[N];

void add(int a, int b, int c)
{
    edge[++tot] = b, weight[tot] = c;
    ne[tot] = head[a], head[a] = tot;
}

bool bfs() // 通过bfs找到增广路，维护增广路上的残存容量
{
    memset(vis, 0, sizeof(vis));
    memset(d, 0, sizeof(d));
    memset(pre, 0, sizeof(pre));
    queue<int> q;

    vis[s] = true, d[s] = 0x3f3f3f3f, q.push(s);    
    while (q.size())
    {
        int x = q.front();
        q.pop();
        for (int i = head[x]; ~i; i = ne[i])
        {
            int y = edge[i];
            if (!vis[y] && weight[i] > 0)
            {
                vis[y] = true;
                d[y] = min(d[x], weight[i]);
                pre[y] = i;
                if (y == t)
                    return true;
                q.push(y);
            }
        }
    }
    return false;
}

int EK()
{
    int res = 0;
    while (bfs())
    {
        res += d[t];
        for (int i = t; i != s; i = edge[pre[i] ^ 1])
        {
            int id = pre[i];
            weight[id] -= d[t];
            weight[id ^ 1] += d[t];
        }
    }
    return res;
}