图论1（c++）

合集 - 学习笔记(2)

1.图论1（c++）06-02

2.动态规划DP：基础，区间，树形DP（c++）08-04

收起

零、前言

作者是 xxs ，图论学得不多，文章有错误还请指出。

一、图的存储与遍历

存储

存图有多种方法，都不复杂，很容易实现。

1.邻接矩阵

直接使用二维数组 graph[N][N] 来存，它虽然代码简单，查询较快，但是有时候很浪费空间，而且数据范围有较大的限制，并不常用。

2.邻接表

顾名思义，邻接表就是 每个节点值储存它直接可以到的其他节点 。

它的空间浪费比邻接矩阵小得多，但是，在找邻居的时候，要遍历它的整个邻接表，速度比邻接矩阵慢。

3.链式前向星

它其实就是用链表实现的邻接表。

主体一个 head[u] 数组，指向 u 的邻居存的地址。
和一个 struct Edge{int to,nxt}; ，其中， to 指邻居编号， nxt 指下一个邻居的地址。

具体代码如下：

点击查看代码

struct Edge{int nxt,to;}e[N*2];
int head[N*2];
void init(){
    cnt=0;
    for(int i=0;i2;i++)e[i].nxt=-1,head[i]=-1;
}
void addedge(int a,int b){
    e[++cnt].to=b;
    e[cnt].nxt=head[a];
    head[a]=cnt;
}
...
for(int i=1;i>u>>v;
    addedge(u,v);
    addedge(v,u);
}

4.Vector 直接存边

这个方法是最常用的一个。

直接用 vector e[N] 存边就可以了。

struct Edge{int to,w;};
vector e[N];
...

遍历

这里只介绍后两种常见方法的遍历方法，前两种请读者自行探讨。

链式前向星

for(int i=head[u];~i;i=e[i].nxt){
    ...
}

Vector 直接存边

for(auto it:e[u]){
    ...
}

---

那么，学会存图和遍历后，来做一下几道模板题来练一练吧：

• 图的存储与出边的排序
• 图的遍历

二、拓扑排序

首先，你要了解拓扑在干什么：

给一个有向无环图(DAG)的所有节点排序————OI_WIKI

那么，拓扑排序之后，就一定有：

• 每个顶点仅出现一次；
• 对于有向边 A->B，在序列中都必有 A 在B前。

操作还是比较简单的：

• 1.找到入度为 $0$ 的点并输出；
• 2.将所有与该点连接的边删除，邻居入度减 $1$；
• 3.重复步骤 1~2 ,直到没有任何点入度为 $0$ 为止。

$\mathrm{注}\mathrm{意}：\mathrm{有}\mathrm{环}\mathrm{图}\mathrm{是}\mathrm{不}\mathrm{能}\mathrm{进}\mathrm{行}\mathrm{拓}\mathrm{扑}\mathrm{排}\mathrm{序}\mathrm{的}！！$

学了拓扑，还是做一道模板题吧：
【模板】拓扑排序/家谱树

三、欧拉路

欧拉路其实就是一个简单的一笔画问题。

它的定义是：从图中某一个点出发，遍历整个图，图中每一条边通过且仅通过一次。
欧拉回路就是起点和终点一样的欧拉路。

一般关于欧拉路的问题基本上就是：

• 是否有欧拉路。
• 打印欧拉路。

通常是通过处理度来解决问题的。

其中，度数为奇数的为奇点，度数为偶数的为偶点。

1.存在性判断

无向图

若全是偶点，存在欧拉回路，显然。
若有 $2$ 个奇点，存在欧拉路，一个是起点，另一个是终点。

有向图

和无向图差不多，我们将一个点的度数记作入度减去出度。

若所有点度数为零，才会存在欧拉回路。
若仅有一个点度数为 $1$，一个点度数为 $-1$，其余点的度数为零，才存在欧拉路，$1$ 的为起点，$-1$ 的为终点。

2.输出欧拉回路

dfs 即可。

习题

• Luogu:P7771 【模板】欧拉路径
• UVa:10054 The Necklace
• POJ:1780 Code

四、连通性问题

关于连通性：

• 连通：对于无向图的两点 $u,v$ ，若存在途径使得 $v_0=u$ 且 $v_k=v$，则称 $u,v$ 连通。
• 连通图：任意两点连通的无向图称为连通图。

1.无向图

一些定义：

• 割点：对于 $G=(V,E)$，$x\in V$,若删去 $x$ 以及关联的边后，图分裂为两个及以上不相连的子图，则称 $x$ 为 $G$ 的割点。
• 割边（桥）：同上。

首先，我们要会求割点和割边：

很明显考虑 Tarjan 算法。

求割点 【模板】割点（割顶）

依赖一下两个主要的数组：

• 追溯值 $lo{w}_x$ ：定义为以 $x$ 为根的搜索树上的点以及通过一条不在搜索树上的边能达到的结点中的最小编号。
• 时间戳 $df{n}_x$ ：定义为 $x$ 按访问顺序的编号。

void Tarjan(int u){
    dfn[u]=low[u]=++Time;
    int son=0;
    for(auto v:e[u]){
        if(dfn[v]){
            low[u]=min(low[u],dfn[v]);
            continue;
        }
        son++;
        Tarjan(v);
        low[u]=min(low[u],low[v]);
        if(low[v]>=dfn[u]&&u!=root)cnt+=!is_cut[u],is_cut[u]=1;
    }
    if(son>=2&&u==root)cnt+=!is_cut[u],is_cut[u]=1;
}

求割边 【模板】割边（桥）

和割点很像：

void tarjan(int u,int fa){
    dfn[u]=low[u]=++idx;
    for(int v:g[u]){
        if(!dfn[v]){
            tarjan(v,u);
            low[u]=min(low[u], low[v]);
            if(dfn[u]add_bridge(u,v);
        }
        else if(v!=fa)low[u]=min(low[u],dfn[v]);
    }
}

习题：

• Luogu:P3469 [POI 2008] BLO-Blockade
• HDU:2460 Network
• Luogu:P1173 [NOI2016] 网格(hehe)

割点和割边可以引出以下这些更为重要的定义：

• 点双连通图：不存在割点的无向连通图称为点双连通图。
• 边双连通图：不存在割边的无向连通图称为边双连通图。
• 点双连通分量：一张图的极大点双连通子图称为点双连通分量（v-DCC），简称点双。
• 边双连通分量：一张图的极大边双连通子图称为边双连通分量（e-DCC），简称边双。

但是，实际上，点双的定义是有歧义的，而笔者采用的是接下来的这一个 OI_WIKI 版本的定义，笔者以后的代码书写也参考接下来的版本。

在一张连通的无向图中，对于两个点 $u$ 和 $v$，如果无论删去哪一个点（不能删 $u$ 和 $v$ 自己）都不能使它们不连通，我们就说 $u$ 和 $v$ 点双连通。——OI_WIKI

求边双 【模板】边双连通分量

边双连通分量的求法很简单。并不比求割边的代码长太多，依旧依赖一下两个主要的数组：

• 追溯值 $lo{w}_x$
• 时间戳 $df{n}_x$

在求割边的时候，我们已经对所有割边进行了标记。
所以我们只要再次 DFS ，不访问割边，对每一各连通块进行标记，则可以得到边双。

边双缩点

考虑一道例题：
POJ:3352 Road Construction

这道题我们考虑缩点。

我们先找出图中的边双，将它们都看成一个个的点，这样会形成一棵树。

那么问题就变成了：一棵树上，增加多少条边可以将其变成一个边双。

答案是叶子节点个数加一再除以二。

原因

由于每两个叶子节点相连后就会形成回路，所以连叶子可以满足形成点双。 而如果连另外的点，就会遗漏叶子，不够优，所以连叶子最优。

求点双 【模板】点双连通分量

点双联通分量的求法就没有边双那么简单了。虽然割边不隶属于任何边双，但是割点是有可能隶属于多个点双的。

所以此时我们就应该在跑 Tarjan 的过程中维护一个栈。

• 当一个节点第一次被访问时，入栈。
• 当 dfn[x]<=low[y] 成立时，不断弹栈，直至 $y$ 被弹出。而且刚刚弹掉的节点和 $x$ 构成一个 v-DCC 。

习题：

边双：

• Luogu P2860 [USACO06JAN] Redundant Paths G

点双：

• Luogu:P3225 [HNOI2012] 矿场搭建
• POJ:2942 Knights of the Round Table
• Luogu:P5058 [ZJOI2004] 嗅探器

2.有向图

一些定义：

• 强连通：若一张有向图的节点两两互相可达，则称这张图是强连通的。
• 强连通分量：即极大的强连通子图，称为SCC。

首先，我们要了解 DFS 生成树。

我们在一个有向图上选一点 $r$ ，从 $r$ 开始遍历，每一个点只遍历一次，这样就会构成一棵树，即 DFS 生成树。

这棵树上会有这么几种边：

• 树边：每次由⼀个已遍历的点到达未遍历的点，就形成了⼀条树边。
• 返祖边：也叫做回边，指向该节点的祖先。
• 横叉边：搜索时遇到⼀个已访问的节点，但这个节点并不是该节点的祖先。
• 前向边：访问时遇到⼦树中的节点时形成的。

举个栗子，如图：

图中的红边即为返祖边，紫边为横插边，黄边为前向边，其余为树边。

求强连通分量有很多方法，由于作者很菜，本文只介绍 $1$ 种。

Tarjan 算法 【模板】强连通分量

这个算法依旧是用栈来处理。

DFS 流程很简单：

• 我们把当前节点 $u$ 入栈。
• 若 $df{n}_u=lo{w}_u$ ，则开始弹栈，直到 $u$ 被弹出去。
• 弹出去的点构成一个 SCC。

代码：

void dfs(int u){
    dfn[u]=low[u]=++Dfn;
    in_stack[u]=1;
    s[++num]=u;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(!dfn[v]){
            dfs(v);
            low[u]=min(low[u],low[v]);
        }
        else{
            if(in_stack[v])low[u]=min(low[u],low[v]);
        }
    }
    if(low[u]==dfn[u]){
        cnta++;
        ans[cnta].push_back(u);
        while(s[num]!=u){
            belong[s[num]]=cnta;
            in_stack[s[num]]=0;
            ans[cnta].push_back(s[num]);
            num--;
        }
        num--;
        belong[u]=cnta;
        in_stack[u]=0;
    }
}

习题

• Luogu:P3387 【模板】缩点
• Luogu:P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G
• Luogu:P1726 上白泽慧音
• Luogu:P11676 [USACO25JAN] DFS Order P
• Luogu:P2863 [USACO06JAN] The Cow Prom S
• Luogu:P2515 [HAOI2010] 软件安装
• Luogu:P5163 WD与地图(请谨慎尝试。。。)
• HDU:3394 Railway
• HDU:1530 Maximum Clique

五、2-SAT

定义

给你 $n$ 个布尔方程，每个方程和两个变量相关，比如 $a\vee b$，表示 $a,b$ 至少满足一个（如果看不懂去学学集合）；然后判断是否有可行的方案，显然是有多种的，一般题目只要求出一种就行。

讲个故事举一个栗子吧：
从前机房里面有 Tri,tty,hzk 三个 OIer，他们对于考试 std 代码的码风有这样那样的要求：

• Tri：我要求代码当中满足下列条件之一：
  1.代码不打空格。（$\mathrm{\neg }a$）
  2.不用快读。（$\mathrm{\neg }b$）
  3.大括号换行。（$c$）
• tty：我要求代码当中满足下列条件之一：
  1.代码打空格。（$a$）
  2.用快读。（$b$）
  3.大括号不换行。（$\mathrm{\neg }c$）
• hzk：我要求代码当中满足下列条件之一：
  1.代码打空格。（$a$）
  2.用快读。（$\mathrm{\neg }b$）
  3.大括号换行。（$c$）

于是，我们可以把三位 OIer 的要求简化为一下这个式子：
$(\mathrm{\neg }a\vee \mathrm{\neg }b\vee c)\wedge (a\vee b\vee \mathrm{\neg }c)\wedge (a\vee \mathrm{\neg }b\vee c)$。

接下来，我们只需要给 $a,b,c$ 三个量赋布尔值就可以解决三位 OIer 的要求。

2-SAT 就是每个 OIer 只有两个条件，比如剔除 $c,\mathrm{\neg }c$ 的存在，就变成了：
$(\mathrm{\neg }a\vee \mathrm{\neg }b)\wedge (a\vee b)\wedge (a\vee \mathrm{\neg }b)$。

解决方法

由于这个东西划分在了图论模块，所以我们用图论解决。

我们用强连通分量。

对于每一个量 $x$，我们建两个点 $x,\mathrm{\neg }x$。
对于每一个 $a\vee b$ 的关系，我们建两条边 $\mathrm{\neg }a\to b\wedge \mathrm{\neg }b\to a$。

你可以将其理解为若 $a$ 假则 $b$ 真，若 $b$ 假则 $a$ 必真。

然后按照箭头的方向建有向边即可。

那么，上面三位 OIer 的要求就可以画成以下这么个图：

同一强连通分量内的变量值一定是相等的。所以就有黄色的两个布尔值相等，橙色的两个也相等。这样就可以解决问题了。

但是，如果 $a$ 和 $-a$ 在同一个强连通分量里，这个东东就无解，很显然吧。。。

对每个变量取所在强连通分量拓扑序较大的那个对应点，就能构造出一组合法解。

后面这个求出解的过程并不是那么显然的，可能要动（fei）一（yi）动（fei）脑子，具体的论证比较麻烦，但学学也不是不行。
想学点击查看这一篇 Luogu 的文章