1. Toy模板网首页
  2. > Toy博客

算法模板（3）：搜索（4）：高等图论

10月前 作者：zhezhidashi 分类：Toy博客 阅读(43) 违法举报

这篇具有很好参考价值的文章主要介绍了算法模板（3）：搜索（4）：高等图论。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

高等图论

有向图的强连通分量

相关概念

  • 强连通分量：Strongly Connected Component (SCC).
  • 对于一个有向图顶点的子集 S S S，如果在 S S S 内任取两个顶点 u u u 和 v v v，都能找到一条 u u u 到 v v v 的路径，那么称 S S S 是强连通的。
  • 如果在强连通的顶点集合 S S S 中加入其他任意顶点集合后，它都不再是强连通的，那么称 S S S 是原图的一个强连通分量。任意有向图都可以分解成若干不相交的强连通分量，这就是强连通分量的分解。将分解后的强连通分量缩成一个顶点，就得到一个 D A G DAG DAG（有向无环图，也叫拓扑图）。

dfn[x] ：结点 x 第一次被访问的时间戳 (dfs number); low[x] ：结点 x 所能访问到的点的 dfn 值的最小值. 这里的树指的是 DFS 树. 所有结点按 dfn 排序即可得 dfs 序列

一个结点的子树内结点的 dfn 都大于该结点的 dfn。从根开始的一条路径上的 dfn 严格递增。一棵 DFS 树被构造出来后，考虑图中的非树边。前向边 (forward edge)：祖先→儿子。后向边 (backward edge)：儿子→祖先。横叉边 (cross edge)：没有祖先—儿子关系的。注意：横叉边只会往 dfn 减小的方向连接。在无向图中，没有横叉边（因为无向图的横插边一定有）、

在构造 dfs 树的时候，称 d f s dfs dfs 尚未搜索到的边为树枝边

1174. 受欢迎的牛

  • Tarjan算法求强连通分量
  • x x x 是正在搜索的节点。看看它是否在强连通分量之中。情况1：存在后向边，指向祖先节点；情况2：存在横叉边，横叉边再走到祖先节点。
  • 时间戳：对于每个点，定义两个时间戳。 d f n [ u ] dfn[u] dfn[u] 表示遍历到u的时间戳； l o w [ u ] low[u] low[u] 表示从 u u u 开始走，所能遍历到的最小时间戳。 u u u 是其所在强连通分量的最高点等价于 d f n [ u ] = l o w [ u ] dfn[u] = low[u] dfn[u]=low[u].
  • 最后连通分量编号逆序一定是拓扑序，所以其实不用进行拓扑排序。
  • 题意：找到一个图中所有满足这样关系的节点的数量：从图中其他任何节点都可以到达这个节点。
  • 对于这道题，如果不是拓扑图，需要每一个点都 b f s bfs bfs 一遍，复杂度 O ( n 2 ) O(n^2) O(n2)，太高。但是如果是拓扑图的话，如果存在至少两个出度为 0 0 0 的点，那么这两个点相互无法到达，答案就是 0 0 0。但是，如果只有一个出度为 0 0 0 的点，那么答案就是出度为 0 0 0 的这个连通块的大小。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<stack>
using namespace std;
const int maxn = 10010, maxm = 50010;
int h[maxn], e[maxm], ne[maxm], idx;
int N, M, dfn[maxn], low[maxn];
int id[maxn], sz[maxn], out[maxn], timestamp, scc_cnt;
bool in_stk[maxn];
void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
stack<int> stk;

void tarjan(int u) {
//千万别写成 timestamp++ !!!
	dfn[u] = low[u] = ++timestamp;
	stk.push(u), in_stk[u] = true;
	for (int i = h[u]; i != -1; i = ne[i]) {
		int v = e[i];
		if (!dfn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else if (in_stk[v]) low[u] = min(low[u], dfn[v]);
	}
	if (dfn[u] == low[u]) {
		scc_cnt++;
		int v;
		do {
			v = stk.top(); stk.pop();
			in_stk[v] = false;
			id[v] = scc_cnt;
			sz[scc_cnt]++;
		} while (v != u);
	}
}
void solve() {
	for (int i = 1; i <= N; i++) {
		if (!dfn[i]) {
			tarjan(i);
		}
	}
	for (int u = 1; u <= N; u++) {
		for (int i = h[u]; i != -1; i = ne[i]) {
			int v = e[i];
			int a = id[u], b = id[v];
			if (a != b) out[a]++;
		}
	}
	int zero = 0, sum = 0;
	for (int i = 1; i <= scc_cnt; i++) {
		if (!out[i]) {
			zero++;
			sum += sz[i];
			if (zero > 1) {
				sum = 0;
				break;
			}
		}
	}
	printf("%d\n", sum);
}
int main() {
	scanf("%d%d", &N, &M);
	memset(h, -1, sizeof h);
	for (int i = 0; i < M; i++) 
    {
		int a, b;
		scanf("%d%d", &a, &b);
		add(a, b);
	}
	solve();
	return 0;
}

无向图的双连通分量

  • 双连通分量又被称为重连通分量。双连通分量分为两种：边双连通分量（e-DCC）、点双连通分量（v-DCC）。
  • 桥（割边）：假设有连通图G，e是其中一条边，如果G-e是不连通的，则边e是图G的一条割边。此情形下，G-e必包含两个连通分支。
  • 割点：在一个无向图中，如果有一个顶点集合，删除这个顶点集合以及这个集合中所有顶点相关联的边以后，图的连通分量增多，就称这个点集为割点集合。如果某个割点集合只含有一个顶点X（也即{X}是一个割点集合），那么X称为一个割点注意割点至少属于两个连通分量。
  • 若一个无向图中的去掉任意一个节点（一条边）都不会改变此图的连通性，即不存在割点（桥），则称作点（边）双连通图。
  • 一个无向图中的每一个极大点（边）双连通子图称作此无向图的点（边）双连通分量。
  • 用tarjan算法可以求边双连通分量和点双连通分量。

395. 冗余路径

  • 边双连通分量算法
  • 给一个无向连通图，问至少加几条边，可以把这个图变成边双连通分量。
  • 求桥：dfn[u] < low[v]
  • 一个图是边双连通分量，等价于任意两点之间有至少两条相互分离的路径（即两条路径没有一条重合的道路）。
  • 双连通分量内任何两点间都是至少有两条相互分离的路径，因此缩点之后，变成了一个树。设图中度数为1的节点有cnt个，那么最后要加的边是 (cnt + 1) / 2 个。其实就是把叶节点两两相连（如果cnt是奇数就把多余的叶节点随便连一下）。这样，就变成了一个双连通图。
#include<cstdio>
#include<algorithm>
#include<stack>
#include<cstring>
using namespace std;
const int maxn = 5010, maxm = 20010;
int h[maxn], ne[maxm], e[maxm], idx;
int id[maxn], low[maxn], dfn[maxn], timestamp, dcc_cnt;
int N, M, d[maxn];
bool is_bridge[maxm];
void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
stack<int> stk;
// from 记载从哪条边来的。
void tarjan(int u, int from) {
	low[u] = dfn[u] = ++timestamp;
	stk.push(u);
	for (int i = h[u]; i != -1; i = ne[i]) {
		int v = e[i];
		if (!dfn[v]) {
			tarjan(v, i);
			low[u] = min(low[u], low[v]);
			
			//dfn[u] < low[v] 等价于 u 与 v 之间的边是桥。
			if (dfn[u] < low[v]) {
				//双向边的编号是两两成对的。
				is_bridge[i] = is_bridge[i ^ 1] = true;
			}
		}
		
		else if (i != (from ^ 1)) low[u] = min(low[u], dfn[v]);
	}
	if (dfn[u] == low[u]) {
		++dcc_cnt;
		int v;
		do {
			v = stk.top(); stk.pop();
			id[v] = dcc_cnt;
		} while (v != u);
	}
}
int main() {
	scanf("%d%d", &N, &M);
	memset(h, -1, sizeof h);
	for (int i = 0; i < M; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		add(a, b), add(b, a);
	}
	tarjan(1, -1);
	for (int i = 0; i < idx; i++) {
		if (is_bridge[i]) d[id[e[i]]]++;
	}
	int cnt = 0;
	for (int i = 1; i <= dcc_cnt; i++) {
		if (d[i] == 1) cnt++;
	}
	printf("%d\n", (cnt + 1) / 2);
	return 0;
}

1183. 电力

  • 点双连通分量算法
  • 删除图中的一个点之后，连通块最多有多少。
  • 求割点：（1）当u不是根节点时， l o w ( v ) > = d f n ( u ) low(v) >= dfn(u) low(v)>=dfn(u)，则u是割点；当u是根节点时，至少有两个子节点 y i y_i yi​，有 l o w ( y i ) > = d f n ( u ) low(y_i) >= dfn(u) low(yi​)>=dfn(u)
  • 统计原本的连通块儿数量blocks，以及枚举每个连通块儿删掉一个点可以得到的最大的连通块儿数量res，答案就是blocks + res - 1.
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 10010, maxm = 30010;
int h[maxn], e[maxm], ne[maxm], idx;
int N, M, res, blocks, root;
int dfn[maxn], low[maxn], timestamp;
void tarjan(int u) {
	dfn[u] = low[u] = ++timestamp;
	int cnt = 0;
	for (int i = h[u]; i != -1; i = ne[i]) {
		int v = e[i];
		if (!dfn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
			if (low[v] >= dfn[u]) cnt++;
		}
		else low[u] = min(low[u], dfn[v]);
	}
	if (u != root) cnt++;
	res = max(res, cnt);
}
void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int main() {
	while (scanf("%d%d", &N, &M) && N) {
		memset(dfn, 0, sizeof dfn);
		memset(h, -1, sizeof h);
		timestamp = idx = 0;
		for (int i = 0; i < M; i++) {
			int a, b;
			scanf("%d%d", &a, &b);
			add(a, b), add(b, a);
		}
		res = blocks = 0;
		for (root = 0; root < N; root++) {
			if (!dfn[root]) {
				blocks++;
				tarjan(root);
			}
		}
		printf("%d\n", blocks + res - 1);
	}
	return 0;
}

396. 矿场搭建

  • 题意：对于一个无向图，在图中找到一些点集{S}，使得不管取下图中哪一个点，其他点都可以到达{S}中的至少一个点。求问点集大小最小是多少，以及在此条件下的方案总数。
  • 点集大小至少为2；
  • 情况1. 若无割点，不管哪下那个点，图都是连通的，那么点集大小为2；
  • 情况2：有割点的话需要缩点，每个割点单独作为一个点，从每个 v-DCC 向其包含的每个割点连一条边。若v-DCC度数为1，那么需要在改分量非割点的地方设置一个出口；若度数大于1，则无需设置出口。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#include<vector>
using namespace std;
typedef unsigned long long ll;
const int maxn = 1010, maxm = 1010;
int h[maxn], e[maxm], ne[maxm], idx;
int dfn[maxn], low[maxn], dcc_cnt, timestamp;
int N, M, root, kase;
bool is_cut[maxn];
vector<int> dcc[maxn];  //这个存的是每一个连通分量含哪些节点。
void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
stack<int> stk;
void tarjan(int u) {
	dfn[u] = low[u] = ++timestamp;
	stk.push(u);
	if (u == root && h[u] == -1) {
		dcc_cnt++;
		dcc[dcc_cnt].push_back(u);
		return;
	}
	int cnt = 0;
	for (int i = h[u]; i != -1; i = ne[i]) {
		int v = e[i];
		if (!dfn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
			if (dfn[u] <= low[v]) {
				cnt++;
				if (u != root || cnt > 1) is_cut[u] = true;
				dcc_cnt++;
				int y;
				do {
					y = stk.top(); stk.pop();
					dcc[dcc_cnt].push_back(y);
				} while (y != v);
				dcc[dcc_cnt].push_back(u);
			}
		}
		else low[u] = min(low[u], dfn[v]);
	}
}
int main() {
	while (scanf("%d", &M) && M) {
		for (int i = 1; i <= dcc_cnt; i++) dcc[i].clear();
		memset(h, -1, sizeof h);
		memset(dfn, 0, sizeof dfn);
		memset(is_cut, 0, sizeof is_cut);
		while (stk.size()) stk.pop();
		idx = N = dcc_cnt = timestamp = 0;
		for (int i = 0; i < M; i++) {
			int a, b;
			scanf("%d%d", &a, &b);
			add(a, b), add(b, a);
			N = max(a, N), N = max(b, N);
		}
		for (root = 1; root <= N; root++) {
			if (!dfn[root]) tarjan(root);
		}
		ll num = 1;
		int res = 0;
		for (int i = 1; i <= dcc_cnt; i++) {
			int cnt = 0, sz = dcc[i].size();
			for (int j = 0; j < sz; j++) {
				if (is_cut[dcc[i][j]]) cnt++;
			}
			
			if (cnt == 0) {
				if (sz > 1) res += 2, num *= (sz - 1) * sz / 2;
				else res++;
				
			}
			else if (cnt == 1) res++, num *= sz - 1;
		}
		printf("Case %d: %d %llu\n", ++kase, res, num); 
	}
	return 0;
}

欧拉路径和欧拉回路

  • 如果图 G G G 中的一个路径包括每个边恰好一次，则该路径称为欧拉路径 ( E u l e r   p a t h ) (Euler\ path) (Euler path)。

  • 如果一个回路是欧拉路径，则称为欧拉回路 ( E u l e r   c i r c u i t ) (Euler\ circuit) (Euler circuit)。

  • 具有欧拉回路的图称为欧拉图（简称 E E E 图）。具有欧拉路径但不具有欧拉回路的图称为半欧拉图。

  • 无向图（图必须是连通图）：

  1. 存在欧拉路径的充要条件：度数为奇数的点只有0个（起点终点重合）或2个（起点终点不重合）。
  2. 存在欧拉回路的充要条件：度数为奇数的点是0个。
  • 有向图（图必须是连通图）：
  1. 存在欧拉路径的充要条件：要么所有点的入度都等于出度（起点终点重合），要么除了两个点之外，其余所有点的入度等于出度，剩余两个点：一个点出度比入度多1（起点），一个点入度比出度多1（终点）。
  2. 存在欧拉回路的充要条件：所有点的入度均等于出度。

1123. 铲雪车

  • 所有的边都是双向边，而且要看成两条边，因此所有点入读与出度相等，其实就是欧拉回路。就算铲雪车停在一条路的中间，总时间是不会变的。因此只需要算一下所有路长度的两倍就行。
  • 输出的话，格式有要求，要求分钟四舍五入、两位、保留前导零，可以这么做：printf("%.f:%02.f\n", hours, minutes);

1184. 欧拉回路

  • 给定一张图，请你找出欧拉回路，即在图中找一个环使得每条边都在环上出现恰好一次。输入：第一行包含一个整数 t t t， t ∈ { 1 , 2 } t \in \lbrace 1,2 \rbrace t∈{1,2}，如果 t = 1 t = 1 t=1，表示所给图为无向图，如果 t = 2 t = 2 t=2，表示所给图为有向图。第二行包含两个整数 n , m n,m n,m，表示图的结点数和边数。接下来 m m m 行中，第 i i i 行两个整数 v i , u i v_i,u_i vi​,ui​，表示第 i i i 条边（从 1 1 1 开始编号）。如果 t = 1 t = 1 t=1 则表示 v i v_i vi​ 到 u i u_i ui​ 有一条无向边。如果 t = 2 t = 2 t=2 则表示 v i v_i vi​ 到 u i u_i ui​ 有一条有向边。图中可能有重边也可能有自环。
  • 复杂度是 O ( m ) O(m) O(m).
  • 复原欧拉回路边的编号
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 100010, maxm = 400010;
int h[maxn], e[maxm], ne[maxm], idx;
bool used[maxm];
int N, M, ans[maxm / 2], cnt, type, din[maxn], dout[maxn];
void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u) {
	//引用千万不要忘！用引用的目的其实是为了针对自环特别多的情况，可以把父结点的那条边也删掉。
	for (int& i = h[u]; i != -1;) {
		if (used[i]) {
			h[u] = ne[i];  ///注意这个删除节点的操作还是很简洁的！
			continue;
		}
		/*
		这个used[i] = true 必须要带上。因为尽管看似这条边已经删掉了，但是只是对于子节点
		而言。而对于父结点还没有删掉。
		*/
		used[i] = true;
		if (type == 1) used[i ^ 1] = true;
		int t;
		if (type == 1) {
			t = i / 2 + 1;
			if (i & 1) t = -t;
		}
		else t = i + 1;
		int v = e[i];
		i = ne[i];
		dfs(v);
		ans[cnt++] = t;
	}
}
int main() {
	scanf("%d%d%d", &type, &N, &M);
	memset(h, -1, sizeof h);
	for (int i = 0; i < M; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		add(a, b);
		if (type == 1) add(b, a);
		dout[a]++, din[b]++;
	}
	if (type == 1) {
		for (int i = 1; i <= N; i++) {
			if (din[i] + dout[i] & 1) {
				printf("NO\n");
				return 0;
			}
		}
	}
	else {
		for (int i = 1; i <= N; i++) {
			if (din[i] != dout[i]) {
				printf("NO\n");
				return 0;
			}
		}
	}
	//要从至少有一条边节点开始搜索
	for (int i = 1; i <= N; i++) {
		if (h[i] != -1) {
			dfs(i);
			break;
		}
	}
	//cnt < M 意味着图中的边不连通。
	if (cnt < M) {
		printf("NO\n");
		return 0;
	}
	printf("YES\n");
	for (int i = cnt - 1; i >= 0; i--) printf("%d%c", ans[i], i == 0 ? '\n' : ' ');
	return 0;
}

拓扑排序

  • 有向无环图至少存在一个入度为0的点，有环图一定不存在拓扑序。

  • 若一个由图中所有点构成的序列A满足：对于图中的每条边(x, y)，x在A中都出现在y之前，则称A是该图的一个拓扑序列。

  • 有向无环图的拓扑序不一定是唯一的。

  • 可以拓扑排序的图，等价于拓扑图，等价于有向无环图(DAG)。

  • 步骤：

  1. 将所有入度为0的点入队q。
  2. while( q.sizse() > 0 )：
    t = q.front(); q.pop();
    for( t 的每一个边 t -> j ):
    d[ j ] --;
    if(d[ j ] == 0) j 入队 q.
  3. 最后，队列中的顺序就是拓扑序。
  • f i l l ( h , h + N , − 1 ) fill(h, h + N, -1) fill(h,h+N,−1)，这样不对，因为节点的编号是从1开始的。老老实实用memset，小心 sizeof 问题，以及测试数据组不能特别多。

1191. 家谱树

  • 输出一个 DAG 的拓扑序
#include<iostream>
#include<queue>
#include<cstring>
const int maxn = 110, maxm = 5010;
using namespace std;
int h[maxn], e[maxm], ne[maxm], idx;
int N, ans[maxn], din[maxn], cnt;
void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void toposort() {
	queue<int> que;
	//首先，把所有入度为0的点加入队列。
	for (int i = 1; i <= N; i++) {
		if (!din[i]) {
			ans[++cnt] = i;
			que.push(i);
		}
	}
	while (que.size()) {
		int u = que.front(); que.pop();
		//接着，每遍历一条u指出的边，就把u指向的顶点的入度减1。直到v的入度为0时再把v加进队列。
		for (int i = h[u]; i != -1; i = ne[i]) {
			int v = e[i];
			din[v]--;
			if (!din[v]) que.push(v), ans[++cnt] = v;
		}
	}
	//若题目数据不能保证一定有解，则最后需要判断cnt == N（总共加进去了N个点）,是的话就存在拓扑序，否则就不存在。
}
int main() {
	scanf("%d", &N);
	memset(h, -1, sizeof h);
	for (int i = 1; i <= N; i++) {
		int t;
		while (cin >> t, t) add(i, t), din[t]++;
	}
	toposort();
	for (int i = 1; i <= cnt; i++) printf("%d%c", ans[i], i == cnt ? '\n' : ' ');
	return 0;
}

1192. 奖金

算法模板（3）：搜索（4）：高等图论文章来源地址https://www.toymoban.com/news/detail-482144.html

  • 关于差分约束的问题：
  1. 若边权任意，则需要用spfa判断环，跑最短路或最长路；
  2. 若边权非负，可以用tarjan算法
  3. 若边权均正，那么可以用拓扑排序跑一遍最长路即可。
    但是还是要掌握下面的，已知拓扑序怎样求最长路。
  • 这道题也让我们明白为什么求最小值要求最长路。而且这道题边不要连反。
法一：先拓扑排序再求最长路
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int maxn = 100010, maxm = 200010;
int N, M;
int h[maxn], e[maxm], ne[maxm], idx;
int d[maxn], din[maxn], topo[maxn], cnt;
void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
bool toposort() {
	queue<int> que;
	for (int i = 1; i <= N; i++) {
		if (!din[i]) {
			que.push(i);
			topo[++cnt] = i;
		}
	}
	while (que.size()) {
		int u = que.front(); que.pop();
		for (int i = h[u]; i != -1; i = ne[i]) {
			int v = e[i];
			din[v]--;
			if (!din[v]) {
				que.push(v);
				topo[++cnt] = v;
			}
		}
	}
	return cnt == N;
}
void topo_longest_path() {
	for (int i = 1; i <= N; i++) d[i] = 100;
	/*
	在拓扑序数组中求最长路一定小心！
	一个是要遍历拓扑序数组，而不是遍历1到N的节点，另一个是，拓扑序中的下标也是1到N，别弄错！
	*/
	for (int j = 1; j <= cnt; j++) {
		int u = topo[j];
		for (int i = h[u]; i != -1; i = ne[i]) {
			int v = e[i];
			d[v] = max(d[v], d[u] + 1);
		}
	}
}
int main() {
    
	memset(h, -1, sizeof h);
	scanf("%d%d", &N, &M);
    
	for (int i = 0; i < M; i++) 
    {
		int a, b;
		scanf("%d%d", &a, &b);
		add(b, a);
		din[a]++;
	}
    
	if (toposort()) 
    {
		topo_longest_path();
		int ans = 0;
		//注意这里还是1~N哈，因为节点的编号是从1到N的。
		for (int i = 1; i <= N; i++) ans += d[i];
		printf("%d\n", ans);
	}
	else printf("Poor Xed\n");
    
	return 0;
}
法二：边拓扑排序边求最长路
void toposort() {
	queue<int> que;
	for (int i = 1; i <= N; i++) {
		if (!din[i]) {
			d[i] = 100;
			que.push(i);
			cnt++;
		}
	}
	while (que.size()) {
		int u = que.front(); que.pop();
		for (int i = h[u]; i != -1; i = ne[i]) {
			int v = e[i];
			din[v]--;
			if (!din[v]) {
				que.push(v);
				d[v] = d[u] + 1;
				cnt++;
			}
		}
	}
	if (cnt != N) printf("Poor Xed\n");
	else {
		int ans = 0;
		for (int i = 1; i <= N; i++) ans += d[i];
		printf("%d\n", ans);
	}
}

164. 可达性统计

  • 给定一张 N N N 个点 M M M 条边的有向无环图，分别统计从每个点出发能够到达的点的数量。 1 ≤ N , M ≤ 30000 1≤N,M≤30000 1≤N,M≤30000
  • 用一个 01 01 01 的二进制串可以很好的表示哪些点可以到这个点。
  • 用 b i t s e t bitset bitset 代替 b o o l bool bool 数组，可以把时间减少到 1 / 32 1 / 32 1/32，因为 b i t s e t bitset bitset 的位数比较少，按位或运算比较快。
  • 这个我是建了反向图，然后宽搜（用到了拓扑排序）。
法一
  • 建反向图，边拓扑排序边求解。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<bitset>
using namespace std;
const int maxn = 30010, maxm = 30010;
int h[maxn], e[maxm], ne[maxm], idx;
int N, M, din[maxn];
bitset<maxn> ans[maxn];
void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void toposort() {
	queue<int> que;
	for (int i = 1; i <= N; i++) ans[i].set(i, 1);
	for (int i = 1; i <= N; i++) {
		if (!din[i]) {
			que.push(i);
		}
	}
	while (que.size()) {
		int u = que.front(); que.pop();
		for (int i = h[u]; i != -1; i = ne[i]) {
			int v = e[i];
			ans[v] |= ans[u], din[v]--;
			if (din[v] == 0) que.push(v);
		}
	}
}
int main() {
	memset(h, -1, sizeof h);
	scanf("%d%d", &N, &M);
	for (int i = 0; i < M; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		add(b, a);
		din[a]++;
	}
	toposort();
	for (int i = 1; i <= N; i++) printf("%d\n", ans[i].count());
	return 0;
}
法二：
  • 先拓扑排序，然后按照拓扑序逆序求解。
toposort();
for (int j = N; j; j--) {
	int u = topo[j];
	f[u][u] = 1;
	for (int i = h[u]; i != -1; i = ne[i]) {
		int v = e[i];
		f[u] |= f[v];
	}
}

2-SAT

朱刘算法

Prufer编码

到了这里，关于算法模板（3）：搜索（4）：高等图论的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 二、搜索与图论6：Dijkstra 模板题+算法模板（Dijkstra求最短路 I, Dijkstra求最短路 II，1003 Emergency）

    二、搜索与图论6：Dijkstra 模板题+算法模板（Dijkstra求最短路 I, Dijkstra求最短路 II，1003 Emergency）

    朴素dijkstra算法 对应模板题：Dijkstra求最短路 I 时间复杂是 O(n^2+m)：n 表示点数，m 表示边数 堆优化版dijkstra 对应模板题：Dijkstra求最短路 II 时间复杂度 O(mlogn)：n 表示点数，m 表示边数 树是一种特殊的图 ，与图的存储方式相同。 对于无向图中的边ab，存储两条有向边a-b, b-a。

    2024年02月14日
    浏览(37)
  • 【算法】复习搜索与图论

    【算法】复习搜索与图论

    🍎 博客主页：🌙@披星戴月的贾维斯 🍎 欢迎关注：👍点赞🍃收藏🔥留言 🍇系列专栏：🌙 蓝桥杯 🌙请不要相信胜利就像山坡上的蒲公英一样唾手可得，但是请相信，世界上总有一些美好值得我们全力以赴，哪怕粉身碎骨！🌙 🍉一起加油，去追寻、去成为更好的自己！

    2024年02月05日
    浏览(46)
  • 【算法入门&图论】【模板】拓扑排序|【模板】单源最短路2 |最小生成树

    【算法入门&图论】【模板】拓扑排序|【模板】单源最短路2 |最小生成树

    ✅作者简介：热爱后端语言的大学生，CSDN内容合伙人 ✨精品专栏：C++面向对象 🔥系列专栏：算法百炼成神 本专栏收录的均为牛客网的算法题目，内含链表、双指针、递归、动态规划、基本数据结构等算法思想的具体运用。牛客网不仅有大量的经典算法题目，也有大厂的面

    2024年02月03日
    浏览(46)

  • 搜索与图论：匈牙利算法

    将所有点分成两个集合，使得所有边只出现在集合之间，就是二分图 二分图：一定不含有奇数个点数的环；可能包含长度为偶数的环， 不一定是连通图

    2024年02月08日
    浏览(65)
  • 搜索与图论（acwing算法基础）

    搜索与图论（acwing算法基础）

    排列数字 n皇后 走迷宫 单链表 点击跳转至例题 idx存的是指针 树与图的深度优先搜索 树的重心 每个节点都是一个单链表 模拟队列 hh = 0 , tt = -1 有向图的拓扑序列 都是从前指向后,即有向无环图（不能有环） 所有入度为0的点，都能排在前面的位置 删掉t-j的边，仅仅是j的入度

    2024年02月08日
    浏览(45)
  • 算法基础课-搜索与图论

    算法基础课-搜索与图论

    题目链接：842. 排列数字 - AcWing题库 思路：写的很好的题解AcWing 842. 排列数字--深度优先遍历代码+注释 - AcWing 也可以考虑使用c++自带的next_permutation函数直接秒了： 题目链接：844. 走迷宫 - AcWing题库 思路：由于bfs是一层一层扩展，所以能保证走到终点时，走过的距离最短，所

    2024年04月15日
    浏览(53)

  • [算法日志]图论： 深度优先搜索(DFS)

    ​ 深度优先搜索算法是一种遍历图这种数据结构的算法策略，其中心思想是朝图节点的一个方向不断跳转，当该节点无下一个节点或所有方向都遍历完时，便回溯朝上一个节点的另一个方向继续遍历。这种搜索策略与回溯法有异曲同工之妙。 正因为和回溯法有相似之处，所

    2024年02月03日
    浏览(63)
  • 【图论算法】深度优先搜索的应用

    【图论算法】深度优先搜索的应用

    深度优先搜索 (depth-first search)是对先序遍历(preorder traversal)的推广。我们从某个顶点 v 开始处理 v，然后递归地遍历所有邻接到 v 的顶点。 对一棵树的所有顶点的访问需 O(|E|) 时间。对任意图进行该过程时则需要考虑避免圈的出现。为此，当访问一个顶点 v 的时候，由于当时已

    2024年02月08日
    浏览(60)
  • 【C++算法模板】图论-拓扑排序，超详细注释带例题

    【C++算法模板】图论-拓扑排序，超详细注释带例题

    推荐视频链接：D01 拓扑排序 给定一张 有向无环图 ，排出所有顶点的一个序列 A A A 满足：对于图中的每条有向边 ( x , y ) (x,y) ( x , y ) ， x x x 在 A A A 中都出现在 y y y 之前，则称 A A A 是该图的顶点的一个拓扑序 拓扑排序 可以判断有向图中是否有环，可以生成拓扑序列 对于下

    2024年04月15日
    浏览(41)

  • acwing算法基础之搜索与图论--kruskal算法

    kruskal算法的关键步骤为： 将所有边按照权重从小到大排序。 定义集合S，表示生成树。 枚举每条边(a,b,c)，起点a，终点b，边长c。如果结点a和结点b不连通（用并查集来维护），则将这条边加入到集合S中。 kruskal算法的时间复杂度为O(mlogm)，它用来解决稀疏图的最小生成树问题

    2024年02月05日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包