图论（一）
|
665
|
0
|
Summary

5668 字
|
36 分钟

怎么建图和图上遍历这种东西就不说了

最短路

  • 松弛操作：如果当前记录的A-B距离比从C绕路走A-C-B距离长，则用后者替换前者的过程

Dijkstra

用一个小根堆（优先队列，给权值取负把大根堆变成小根堆）维护起点到其的最短路长度最小的结点，显然每次取出的点与起点间的最短路已经确定，不会再发生改变（由松弛操作的定义，直连的距离在全局上最短意味着绕路一定更劣）。对它的所有出边执行松弛，重复至最短路长度未确定的点集为空。

void dijkstra(int st){
	for(int i = 1; i <= n; i++) dis[i] = 0x7fffffff;
	memset(vis,false,sizeof(vis));
	dis[st] = 0;
	q.push(mp(0,st));
	while(!q.empty()){
		int x = q.top().y;
		q.pop();
		if(vis[x]) continue;
		vis[x] = true;
		for(int i = head[x]; i; i = e[i].next){
			int y = e[i].to;
			if(dis[y] > dis[x] + e[i].w){
				dis[y] = dis[x] + e[i].w;
				q.push(mp(-dis[y],y));
			}
		}
	}
}

Floyd

求两两之间的最短路，$O(n^3)$

就是先枚举中继点再枚举起点和终点，一一松弛

for(int k = 1; k <= n; k++){
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			if(dis[i][k] + dis[k][j] < dis[i][j]){
				dis[i][j] = dis[i][k] + dis[k][j];
			}
		}
	}
}

SPFA

bellman-ford算法会执行n-1次对所有边松弛的尝试以保证不再能进行新的松弛操作，但是这很慢

显然的，只有上一次被松弛过的点以及它所连接的边才会引起下一次松弛操作（源点到一个点的距离没变显然它不会作为中继点参与新的松弛，因为它作为中继点松弛的可能性之前已经尝试过了），我们可以开一个队列存放已经松弛过的点，这样就不会进行注定无效的尝试了

void spfa(int s){
	for(int i = 1; i <= n; i++){
		vis[i] = false;
		dis[i] = 0x7fffffff;
	}
	queue <int> q;
	q.push(s);
	vis[s] = true;
	dis[s] = 0;
	while(!q.empty()){
		int x = q.front();
		q.pop();
		vis[x] = false;
		for(int i = head[x]; i; i = e[i].next){
			int y = e[i].to;
			if(dis[y] > dis[x] + e[i].w){
				dis[y] = dis[x] + e[i].w;
				if(!vis[y]){
					q.push(y);
					vis[y] = true;
				}
			}
		}
	}
}

最小生成树

一个图的最小生成树是它的一个联通子图，包含原图中的所有结点，并且有保持图联通所需要的最少的边

Kruskal

基本思想就是先把所有的点都丢到一起，然后贪心的加入最短的有效边（一条边称之为有效边，指将它加入图中可以连接本来没有边连接的点）

bool cmp(edge x,edge y){
	return x.w < y.w;
}
int kruskal(){
	int ans = 0,cnt = 0;
	sort(e,e + m + 1,cmp);
	for(int i = 1; i <= m; i++){
		int root1 = find(e[i].u);
		int root2 = find(e[i].v);
		if(root1 == root2) continue;
		ans += e[i].w;
		merge(e[i].u,e[i].v);
		if(++cnt == n - 1) break;
	}
	return ans;
}

Prim

每次选择离已经加入最小生成树的点距离最小且尚未加入的点加入最小生成树，常数比kruskal大所以暂时不打算写

树上问题

树的直径

定义：树上任意两节点间的最长简单路径，显然可以有多条且它们相等

两次dfs

先从任意节点开始一次dfs，到达距其最远的节点$z$，从这个点开始再进行一次的dfs,同样到达距其最远的节点$z^{‘}$，则两次dfs的路径合起来就是这棵树的直径

证明：反证法，记出发点为$y$，真实直径为$\delta(s,t)$，但第一次dfs到达的点$z$不为$s$或$t$，共有三种情况

  • $y$在$\delta(s,t)$上：若有$\delta(y,z) >\delta(y,t)$，又$y$在$\delta(s,t)$上，则有$\delta(s,z) > \delta(s,t)$，与真实直径为$\delta(s,t)$矛盾
  • $y$不在$\delta(s,t)$上，且$\delta(y,z)$与$\delta(s,t)$有重合：若有$\delta(y,z) >\delta(y,t)$，又$y$与$\delta(s,t)$有交点，那么有$\delta(s,z) >\delta(s,t) $，与真实直径为 $ \delta(s,t) $ 矛盾
  • $y$不在$\delta(s,t)$上，且$\delta(y,z)$与$\delta(s,t)$不重合：因为在一棵树上，所以$\delta(y,z)$与$\delta(s,t)$中的点一定有至少一条边相连，设这样的一对点为$x$和$x^{‘}$,那么有$\delta(x,z) > \delta(x,t)$，既然这样，直径应该为$\delta(s,z)$，同样与真实直径为$\delta(s,t)$矛盾
int dis[maxn],c;//c记录离初始点最远的点

void dfs(int u,int fa){
	for(int i = head[u]; i; i = e[i].next){
		int v = e[i].to;
		if(v == fa) continue;
		dis[v] = dis[u] + 1;//加e[i].w
		if(dis[v] > dis[c]) c = v;
		dfs(v,u);
	}
}

dfs(1,0);
dis[c] = 0;
dfs(c,0);
//最后求得的直径就是dis[c]

容易发现，上述证明成立的条件为边权非负

树形DP

记录当1为根时，每个节点作为子树的根向下延伸的最远距离$d_1$和次远距离$d_2$，则直径长度为$max(d_1+d_2)$

int d1[maxn],d2[maxn],d;//d记录max(d_1,d_2)

void dfs(int u,int fa){
	d1[u] = 0;
	d2[u] = 0;
	for(int i = head[u]; i; i = e[i].next){
		int v = e[i].to;
		if(v == fa) continue;
		dfs(v,u);
		if(d1[v] + 1 > d1[u]){//以u为根节点,取v子树能延伸的最远距离比当前记录的最远距离长,更新最远和次远
			d2[u] = d1[u];
			d1[u] = d1[v] + 1;
		}else if(d1[v] + 1 > d2[u]){//以u为根节点,取v子树能延伸的最远距离比当前记录的次远距离长,更新次远
			d2[u] = d1[v] + 1;
		}
	}
	d = max(d,d1[u] + d2[u]);//更新max(d_1[u]+d_2[u])
}

这个是能处理负权边的

树的直径的性质：

  • 若一棵树的边权均为正，则树的所有直径的中点为同一点

树的重心

定义：对树上每一个点，记录它的所有子树（包括向上的子树）中节点最多的那一个的的节点数，这个值最小的点为这棵树的重心

按照定义算出每个点的所有子树中节点最多的那一个的的节点数，向上的子树的节点数 = 整棵树（不是说子树）的大小 – 这个节点向下的所有子树的节点数

int sze[maxn],weight[maxn];//sze是这个点及其所有子树的节点总数,weight是定义中的"它的所有子树（包括向上的子树）中节点最多的那一个的的节点数",称为重量

void dfs(int u,int fa){
	sze[u] = 1;
	weight[u] = 0;
	for(int i = head[u]; i; i = e[i].next){
		int v = e[i].to;
		if(v == fa) continue;
		dfs(v,u);
		sze[u] += sze[v];
		weight[u] = max(weight[u],sze[v]);
	}
	weight[u] = max(weight[u],n - sze[u]);
//	cout << u << ' ' << weight[u] << endl;
	if(weight[u] <= n / 2){
		//puts("ok");
		ans.push_back(u);
	}
}

树的重心的性质：

  • 以树的重心为根时，所有子树的大小都不超过整棵树的一半
  • 树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样。
  • 把两棵树通过一条边相连得到一棵新的树，那么新的树的重心在连接原来两棵树的重心的路径上。
  • 在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离。

LCA

树上的一个点集的最近公共祖先是它们的公共祖先里面离根最远的那个

倍增求LCA

预处理$fa_{x,i}$表示x的第$2^i$个祖先以优化求lca时的跳动过程

在朴素算法的第一阶段，我们要把要求lca的$u,v$两点跳到同一深度。假设它们的深度之差为y，对y二进制拆分可以将跳转优化到$\_\_builtin\_popcount(y)$次（假设dep[u] > dep[v]，那么每次跳到f[u][log2(dep[u] – dep[v])]，$2^{log2(dep[u] – dep[v])}$是小于等于y的最大的2的幂次方）

在第二阶段，我们要同时向上跳转u和v，我们从能取到的最大的i（就是log2(dep[u] – 1)）开始尝试，直到$fa_{u,i} = fa_{v,i}$或i取完0，如果$fa_{u,i} \neq fa_{v,i}$，那么把u跳到$fa_{u,i}$，把v跳到$fa_{v,i}$（因为最近公共祖先的祖先一定是公共祖先，因此不相等就一定没跳过，而且从对i的限制出发也不会跳过头）。这样，在尝试结束时$lca(u,v) = fa_{u,0}$

int dep[maxn],f[maxn][25],lg[maxn];//dep是深度,f是倍增的fa,lg是预处理log2

void dfs(int u,int fa){
	dep[u] = dep[fa] + 1;
	f[u][0] = fa;
	for(int i = 1; (1 << i) <= dep[u]; i++){
		f[u][i] = f[f[u][i - 1]][i - 1];
	}
	for(int i = head[u]; i; i = e[i].next){
		if(e[i].to != fa) dfs(e[i].to,u);
	}
}

int lca(int x,int y){
	if(dep[x] < dep[y]) swap(x,y);
	while(dep[x] > dep[y]){
		x = f[x][lg[dep[x] - dep[y]] - 1];
	}
	if(x == y) return x;
	for(int k = lg[dep[x] - 1]; k >= 0; k--){
		if(f[x][k] != f[y][k]){
			x = f[x][k];
			y = f[y][k];
		}
	}
	return f[x][0];
}

void init(){
	for(int i = 1; i <= n; i++){
		lg[i] = lg[i - 1] + ((1 << lg[i - 1]) == i);//lg[i] = log2(i) + 1
	}
}

最近公共祖先的性质：

  • lca(u) = u（一个点的最近公共祖先就是它本身）
  • u是v的祖先，当且仅当lca(u,v) = u
  • 如果u ,v互相不为祖先，则u ,v分别处于lca(u,v)的两棵不同子树中
  • 对点集S的前序遍历中,lca(S)出现在所有S中元素的最前面，对点集S的后序遍历中,lca(S)出现在所有S中元素的最后。
  • 两点集的并 的最近公共祖先为 两点集各自的最近公共祖先 的最近公共祖先
  • 两点的最近公共祖先必定处在树上两点间的最短路上
  • d(u,v) = h(u) + h(v) – 2h(lca(u,v)) ，d为树上两点间距离,h(node)为node到树根的距离

树链剖分（重链剖分）

把树分割成若干条链的形式，从而方便维护树上路径的信息

重链剖分可以将树上的任意一条路径划分成不超过O(logn)（n为点数）条连续的链，每条链上的点深度互不相同（即是自底向上的一条链，链上所有点的 LCA 为链的一个端点）。除此之外，重链剖分还能保证划分出的每条链上的节点的dfs序（就是dfs遍历树时访问节点的顺序）连续，从而便于使用维护序列的数据结构维护树上路径上的信息

前置定义：

  • 重子节点：一个点的子节点中子树最大（也就是包含的节点数最多）的那一个，如果有多个，任取其一，如果没有子节点，显然没有重子节点
  • 轻子节点：一个点的子结点中除开重子节点外的所有子节点（包括那些子树最大但是没被取用的子节点）
  • 重边：一个点的重子节点到这个点的轻子节点的边
  • 轻边：一个点的轻子节点到这个点的另一个轻子节点的边
  • 重链：若干条首尾相接的重边

如果把落单的轻子节点也看作重链，则整棵树被剖分成了若干条重链

实现：

再来点定义：

  • fa[x]表示节点x的父亲
  • dep[x]表示节点x的深度
  • sze[x]表示节点x的子树大小
  • son[x]表示节点x的重子节点
  • top[x]表示节点x所在重链的顶部（深度最小的）节点
  • dfn[x]表示节点x的dfs序（也用作稍后拿线段树维护它时它在线段树中的编号（因为dfn可以在树中唯一的标记一个点））
  • rk[x]表示dfs序对应的节点编号，有rk[dfn[x]] = x

首先，我们用一次dfs求出fa[x]，dep[x]，sze[x]，son[x]

void dfs1(int x,int fa,int step){//点,父亲,深度
	fa[x] = fa;
	dep[x] = step;//当前深度
	sze[x] = 1;//还没有去找子树,子树大小初始为1(要算它自己)
	for(int i = head[x]; i; i = e[i].next){
		int y = e[i].to;
		if(y == fa) continue;
		dfs1(y,x,step + 1);
		sze[x] += sze[y];//更新子树大小
		if(sze[y] > sze[son[x]]) son[x] = y;//如果当前找到的这个子节点的子树比当前重子节点的子树大,它就是新的重子节点
	}
}

然后，我们用第二次dfs基于之前求出的信息求出top[x]，dfn[x]，rk[x]

void dfs2(int x,int t){//从x开始找重链,当前重链的顶端节点为t
	top[x] = t;//这条重链上所有点在的重链的顶端节点都是t
	cnt1++;//这里叫cnt1是为了避免和链式前向星的cnt冲突
	dfn[x] = cnt1;//这是dfs序,x点第cnt1个被dfs访问到
	rk[cnt1] = x;//就是定义,记录dfs序对应的节点编号
	if(!son[x]) return;//没有重子节点说明没有子节点,这条重链找完了
	dfs2(son[x],t);//有重子节点就继续往下找
	for(int i = head[x]; i; i = e[i].next){//从这条重链上的每一个点出发
		int y = e[i].to;
		if(y != son[x] && y != fa[x]) dfs2(y,y);//e[i].to != son[x]去掉重子节点,e[i].to !- fa[x]去掉父亲,这时每一个轻子节点都可以作为一条新的重链的起点(这个点有子节点就一定有重子节点,前面说了没有子节点的轻子节点也视作重链)
	}
}

重链剖分的性质：

  • 树上每个节点都属于且仅属于一条重链。
  • 重链开头的结点不一定是重子节点（看dfs2遍历连边那个地方）
  • 所有的重链将整棵树完全剖分。
  • 在剖分时重边优先遍历，最后树的dfn上，重链内的dfn序是连续的。按dfn排序后的序列即为剖分后的链
  • 一棵子树内的dfn是连续的（由此可以推知，当我们向下经过一条轻边时，所在子树大小至少除以2，因此把树上任意一条路径拆成从lca分别向两边走，最多要走O(logn)次，即树上每条路径都可以被拆分成不超过O(logn)条重链）

常见应用：

  • 维护路径：以\delta(u,v)为例，对深度较大的端点到它所在重链的顶端的路径进行修改（重链中所有点的dfn连续），然后让它跳到它所在重链的顶端，不断重复这一过程直到两点在同一条链上（一个点在链上，另一个点在这个链的链顶），再进行最后一次修改就完成了对\delta(u,v)的维护\
void add(int x,int y,int v){//以用线段树给u,v的路径加上v为例
	while(top[x] != top[y]){
		if(dep[top[x]] < dep[top[y]]) swap(x,y);
		seg :: add(1,1,n,dfn[top[x]],dfn[x],v);
		x = fa[top[x]];
	}
	if(dfn[x] > dfn[y]) swap(x,y);
	seg :: add(1,1,n,dfn[x],dfn[y],v);
}
  • 维护子树：在dfs2的遍历子节点部分前后各记录一次dfn，这个区间就是包含以这个dfs传入的点为根的子树中的所有点的区间
  • 求LCA（拿树剖求LCA怕不是有什么大病）：用维护路径的方法往上跳，跳到两点在同一条链上时深度较小的那个点就是这两个点的lca

负环与差分约束

负环就是权值为负的环，用能处理负权的最短路算法都能判断（dijkstra不能判断负权环的原因是它的原理为每次确定一个最短距离点，然后用这个点的出边更新到其它点的最短距离，但是负权会导致确定了最短距离点后起点到它的最短距离发生变化，因为有可能存在起点到中继点距离比到最短距离点长但是中继点到最短距离点的距离是个负数的情况）

以SPFA(队列优化的bellman-ford算法为例，我们只需要在松弛时统计经过的边数，若经过的边数大于等于总点数，说明存在负环)

bool spfa(int s){
	for(int i = 1; i <= n; i++){
		vis[i] = false;
		dis[i] = 0x7fffffff;
		inq[i] = 0;
	}
	queue <int> q;
	q.push(s);
	vis[s] = true;
	dis[s] = 0;
	while(!q.empty()){
		int x = q.front();
		q.pop();
		vis[x] = false;
		if(inq[x] >= n) return true;
		for(int i = head[x]; i; i = e[i].next){
			int y = e[i].to;
			if(dis[y] > dis[x] + e[i].w){
				dis[y] = dis[x] + e[i].w;
				if(!vis[y]){
					q.push(y);
					vis[y] = true;
					inq[y]++;
					if(inq[y] >= n) return true;
				}
			}
		}
	}
	return false;
}

差分约束系统是一种特殊的n元一次不等式组，它包含n个变量$x_1…x_n$以及m个约束条件，每个约束条件是由两个变量的差构成的，形如$x_i – x_j \leq c_k$，其中$1 \leq i,j \leq n,i \neq j,i\leq k\leq m$且$c_k$为常数，我们的目的是求一组解$x_1 = a_1,x_2 = a_2…x_n=a_n$满足全部约束条件或者判断解不存在

观察差分约束系统的约束条件：$x_i – y_i \leq c_k$，变形得到$x_i \leq c_k + y_i$，与求最短路的松弛操作所使用的三角形不等式$dis[x] \leq dis[y] + e[i].w$相似

以一个简单的三角形不等式为例

$$
B- A \leq c\\ C – B \leq a\\ C – A \leq b
$$

由此可以得到有关C-A的约束：$C – A \leq b $、$C – A \leq c + a$，因此有$C – A \leq min(b,c + a)$即$max(C – A) = min(b,c – a)$

如果把A、B、C看作点，a、b、c看作各点对边的边权，那么$max(C – A) = min(b,c – a)$刚好可以看作C到A的最短路，我们将其推广，对约束条件$x_i – x_j \leq c_k$，我们从j到i连接一条长度为$c_k$的有向边

显然，如果$a_1,a_2,…,a_n$是该差分约束系统的一组解，那么给每一个元加上一个相同的常数d所得$a_1+d,a_2+d,…,a_n+d$也是该差分约束系统的一组解

我们设$dis[0] = 0$并从点$0$（差分约束系统种没有点$0$）向每一个点连一条权值为0的边，跑单源最短路，如果存在负环说明此差分约束系统无解，否则$a_i = dis[i]$为此差分约束系统的一组解

同余最短路

遇到形如“给定$n$个整数，求这$n$个整数能拼凑出多少的其他整数（$n$个整数可以重复取）”，以及“给定$n$个整数，求这$n$个整数不能拼凑出的最小（最大）的整数”，或者“至少要拼几次才能拼出模$K$余$p$的数”的问题时，可以通过同余最短路的方法大幅度优化复杂度

以LuoguP3403 跳楼机为例，这道题是第一类问题的一个简单模板。

显而易见的，如果你用$n-1$个整数拼凑出了一些其他整数，那么这些整数加上最后剩下的那一个整数的任意倍得到的数都可以被这$n$个数拼凑出来。假设剩下的那个整数为$x$，那么我们枚举$[0,x)$中的数i以及剩下的$n-1$个整数$c_i$，在$i$和$(i + c_i)$之间连接长度为$c_i$的有向边，从$0$开始跑单源最短路，$dis[i]$就是从$0$开始能凑出的最小的膜$x$余$i$的数（这里可以看出$x$选这$n$个整数中最小的那一个在空间上最优），接下来就可以用数学方法计算结果了

Tarjan与有向图的连通性

前置：强连通分量

强连通：有向图$G$强连通，当且仅当$G$中任意两个节点联通

强连通分量：极大的强连通子图

前置：dfs生成树

dfs遍历有向图时产生边的四种类型（当然对于一张特定的图这四种边不一定全部出现）：

  • 树边：每次搜索找到一个还没有访问过的节点时生成的边（这些边的集合所构成的树称为该有向图的dfs生成树）
  • 反祖边：指向当前节点的祖先节点的边
  • 横叉边：指向已经访问过,但不是当前节点的祖先节点的节点的边
  • 前向边：指向当前节点的子树中的节点的边（就是在当前节点的一个子节点加入dfs树后从当前节点直接访问它所产生的边）

考虑dfs生成树与强连通分量之间的关系：如果节点u时某个强连通分量在dfs生成树中遇到的第一个节点，那么这个强连通分量的其余节点肯定在dfs生成树中以u为根的子树中

Tarjan求强连通分量

基本思路：对每个点找到那些与它一起能构成环的所有节点

以点对(x,y)为例，容易发现,前向边对找强连通分量没啥作用,因为树边的存在性就已经确保了一定存在x到y的路径。而反祖边是非常有意义的，两个点之间存在反祖边则它们一定在一个环中（因为正向路径肯定存在）。横叉边也是一个有用的东西，如果存在一条从x连向y的横叉边，而y又存在一条连向x或x的祖先的路径，那么它们也能形成环

为了找到这样的环已经组成它的所有节点，tarjan算法在深度优先遍历图的同时维护了一个栈，在访问到节点x时，栈中存放有有可能与从x出发的后向边和横叉边形成环的全部节点

先来两个定义：

  • $dfn[x]$表示节点x的dfs序
  • $low[x]$表示能回溯到的dfn最小且与x成环的节点的dfn，即存在有向边从x的子树中的节点指向它的栈中节点（也就是先维护可能成环的全部节点，然后用真的成环了的那些去更新low）

根据定义,求强连通分量的tarjan算法本质上是一个变（mo）形（gai）的图的深度优先遍历，当第一次访问到节点x时，把x入栈，初始化$low[x]=dfn[x]$，随后扫描与x相连的所有节点y，如果y还没被访问过，说明(x,y)是一条树边，递归访问y,回溯后尝试用$low[y]$更新$low[x]$，若y被访问过且y在栈中，说明y与x可以成环，直接尝试用$dfn[y]$更新$low[x]$。在从x回溯之前，判断$low[x]$是否等于$dfn[x]$，如果$low[x]=dfn[x]$，说明栈中x以及比它后入栈的节点构成一个强连通分量（如果$low[x]=dfn[x]$，说明从x出发通过比它后入栈的这些节点能走回x,正是强连通分量的定义），把这些点弹出并记录即可得到图中的一个强连通分量

int head[maxn][15],cnt[15];//多个邻接表
int dfn[maxn],low[maxn],c[maxn],v[maxn];//dfn是dfs序,low的定义在前文中,c是点所在scc的编号,v是点权
int cnt1 = 0,num = 0;//cnt1是求dfn用的,num是scc的数目
bool instack[maxn];
stack <int> st;
vector <int> scc[maxn];//存放单个强连通分量中的点

struct edge{
	int to;
	int next;
}e[maxm][15];//多个邻接表

void add_edge(int u,int v,int i){//i维度是要加的邻接表的编号
	cnt[i]++;
	e[cnt[i]][i].to = v;
	e[cnt[i]][i].next = head[u][i];
	head[u][i] = cnt[i];
}

void tarjan(int u){
	cnt1++;
	dfn[u] = cnt1;
	low[u] = dfn[u];
	st.push(u);
	instack[u] = true;
	for(int i = head[u][1]; i; i = e[i][1].next){
		int y = e[i][1].to;//如果有边连向父亲,显然父亲已经入栈了,不会再进入递归,因而不会死循环
		if(!dfn[y]){//y还没被访问过
			tarjan(y);
			low[u] = min(low[u],low[y]);
		}else if(instack[y]){
			low[u] = min(low[u],dfn[y]);
		}
	}
	if(dfn[u] == low[u]){
		num++;
		while(st.top() != u){
			instack[st.top()] = false;
			c[st.top()] = num;
			scc[num].push_back(st.top());
			st.pop();
		}
		instack[st.top()] = false;
		c[st.top()] = num;
		scc[num].push_back(st.top());
		st.pop();
	}
	return;
}

for(int i = 1; i <= n; i++){
	if(!dfn[i]) tarjan(i);//一次只能扫出一个强连通分量/单个点,因此要检查所有点是否有dfn以确保扫过所有点
}

常见应用：

  • 缩点：求强连通分量的时候记录的每个点所在的强连通分量的编号，因此我们只要新开一个邻接表，如果两个点之间存在有向边且它们所在的强连通分量编号不同，那么就直接把这两个强连通分量连起来，如果有边权，视题目具体情况处理（而在同一个强连通分量中的点一定是可以互相抵达的）

二分图

如果一张无向图的N个节点可以分成两个交集为空的非空集合，并且属于同一个集合的点之间没有边连接，则称这张图为二分图

二分图的判定：染色法

定理：一张无向图是二分图，当且仅当这张图中不存在奇环（长度为奇数的环）（即这是充要条件）

尝试用两种颜色标记图中的节点，当一个节点被标记后，与它相连的点显然应标记为与它不同的颜色，如果存在冲突，说明有奇环。

bool dfs(int x，int c){
	col[x] = c;
	for(int i = head[x]; i; i = e[i].next){
		int y = e[i].to;
		if(col[y] == -1){
			if(!dfs(y，c ^ 1)) return false;
		}else{
			if(col[y] != c ^ 1) return false;
		}
	}
	return true;
}
复健
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																				
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇