数据布局与算法-图论-复习2（差分束缚，强连通分量，二分图，LCA，拓扑排序，欧拉路径和欧拉回路）
7. 差分束缚原理
差分束缚体系是一种特别的不等式组，形如 xi−xj≤c。可以将其转化为图论中的最短路或最长路问题。
最短路求最大值：当我们要找出满足全部不等式的最大解时，使用最短路算法。对于不等式 xi−xj≤c，可以转化为 xi≤xj+c，这雷同于最短路中的松懈操作 dist≤dist+w(j,i)，所以建图时从 j 到 i 连一条权值为 c 的边，然后通过最短路算法求解。
最长路求最小值：当要找出满足全部不等式的最小解时，使用最长路算法。对于不等式 xi−xj≥c（可由 xj−xi≤−c 变形得到），转化为 xi≥xj+c，雷同最长路的松懈操作 dist≥dist+w(j,i)，建图时从 j 到 i 连一条权值为 −c 的边，用最长路算法求解。
过程
通常需要参加一个超级源点，将超级源点与全部节点相连，边权为 0，以包管图是连通的，然后举行对应的最短路或最长路算法。
代码：
#include <iostream>#include <vector>#include <queue>#include <climits>using namespace std;
const int MAXN = 1005;struct Edge {
int to, w;};
vector<Edge> adj;int dist;bool in_queue;
// 最长路算法（求最小值）bool spfa(int s, int n) {
fill(dist, dist + MAXN, INT_MIN);
fill(in_queue, in_queue + MAXN, false);
dist = 0;
queue<int> q;
q.push(s);
in_queue = true;
while (!q.empty()) {
int u = q.front();
q.pop();
in_queue = false;
for (auto : adj) {
if (dist < dist + w) {
dist = dist + w;
if (!in_queue) {
q.push(v);
in_queue = true;
}
}
}
}
return true;}
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int i, j, c;
cin >> i >> j >> c;
// 求最小值，建图 j -> i, cost: -c
adj.push_back({i, -c});
}
// 参加超级源点 0
for (int i = 1; i <= n; i++) {
adj.push_back({i, 0});
}
if (spfa(0, n)) {
for (int i = 1; i <= n; i++) {
cout << dist << " ";
}
cout << endl;
}
return 0;}
8. 有向图的强连通分量
floyd很好理解，本身就是一个用来解决转达闭包的算法
tarjan：通过dfn和low数组，利用dfs的方式找出强连通分量
注意：tarjan得到的序号的逆序就是拓扑序
Floyd 算法
Floyd 算法本身是用于求解全源最短路的算法，但也可以用于解决转达闭包问题。转达闭包是指对于图中的任意两个节点 i 和 j，判断是否存在从 i 到 j 的路径。
代码：
#include <iostream>#include <vector>using namespace std;
const int MAXN = 1005;bool graph;
void floyd(int n) {
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
graph = graph || (graph && graph);
}
}
}}
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
graph = true;
}
floyd(n);
// 输出转达闭包结果
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cout << graph << " ";
}
cout << endl;
}
return 0;}
Tarjan 算法
Tarjan 算法通过深度优先搜索（DFS）和两个数组 dfn 和 low 来找出有向图中的强连通分量。
dfn：表现节点 u 在 DFS 过程中的时间戳，即第一次访问节点 u 的顺序。
low：表现节点 u 能够回溯到的最早的节点的时间戳。
代码：
#include <iostream>#include <vector>#include <stack>using namespace std;
const int N = 10005;
vector<int> graph;int dfn, low, index = 0;bool inStack;
stack<int> st;int color, cnt = 0;
void tarjan(int u) {
dfn = low = ++index;
st.push(u);
inStack = true;
for (int v : graph) {
if (!dfn) {
tarjan(v);
low = min(low, low);
} else if (inStack) {
low = min(low, dfn);
}
}
if (dfn == low) {
cnt++;
while (true) {
int v = st.top();
color = cnt;
st.pop();
inStack = false;
if (v == u) break;
}
}}
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
graph.push_back(v);
}
for (int i = 1; i <= n; i++) {
if (!dfn) {
tarjan(i);
}
}
// 输出每个节点所属的强连通分量编号
for (int i = 1; i <= n; i++) {
cout << "Node " << i << " belongs to SCC " << color << endl;
}
return 0;}
9. 二分图
染色法判定二分图
二分图是指可以将图中的节点分成两个不相交的集合 A 和 B，使得图中的每条边的两个端点分别属于 A 和 B。染色法的基本思想是对图中的节点举行染色，相邻节点染不同的颜色，如果在染色过程中发现相邻节点颜色相同，则该图不是二分图。
代码：
#include <iostream>#include <vector>using namespace std;
const int MAXN = 10005;
vector<int> adj;int color;
bool dfs(int u, int c) {
color = c;
for (int v : adj) {
if (color == c) {
return false;
}
if (color == 0) {
if (!dfs(v, 3 - c)) {
return false;
}
}
}
return true;}
bool isBipartite(int n) {
fill(color, color + MAXN, 0);
for (int i = 1; i <= n; i++) {
if (color == 0) {
if (!dfs(i, 1)) {
return false;
}
}
}
return true;}
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj.push_back(v);
adj.push_back(u);
}
if (isBipartite(n)) {
cout << "The graph is bipartite." << endl;
} else {
cout << "The graph is not bipartite." << endl;
}
return 0;}
匈牙利算法求最大边匹配
匈牙利算法的核心思想是不绝探求增广路径，通过互换匹配边和非匹配边来增加匹配的边数。
景象模拟：
女生开始找男朋侪，女生i对m个男生故意思，
她就从头开始问这m个男生:
如果1，这个男生没有女朋侪，她就和她构成情侣，
如果2，这个男生有女朋侪，他们实验为他现在的女朋侪找一个新的并且这个男生的女朋侪中意的新的男朋侪。
如果上面的两次实验都失败了，她就去看下一个她中意的。
如果逛了一圈都没有她中意的，她就是一个剩女了
最大边匹配，最小路径点覆盖，最大独立集，最小路径重复点覆盖概念是什么。
他们的关系：最大边匹配=最小路径点覆盖， 最大独立集=最小路径重复点覆盖=点总数-最大匹配边
代码：
#include <iostream>#include <vector>#include <cstring>using namespace std;
const int MAXN = 1005;
vector<int> adj;int match;bool vis;
bool dfs(int u) {
for (int v : adj) {
if (!vis) {
vis = true;
if (match == 0 || dfs(match)) {
match = u;
return true;
}
}
}
return false;}
int hungarian(int n) {
int ans = 0;
memset(match, 0, sizeof(match));
for (int i = 1; i <= n; i++) {
memset(vis, false, sizeof(vis));
if (dfs(i)) {
ans++;
}
}
return ans;}
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj.push_back(v);
}
int max_match = hungarian(n);
cout << "The maximum matching size is: " << max_match << endl;
return 0;}
相关概念
最大边匹配：二分图中匹配边的最大数量。
最小路径点覆盖：在有向无环图中，用最少的不相交路径覆盖全部节点。对于二分图，最大边匹配数等于最小路径点覆盖数。
最大独立集：图中最大的节点集合，使得集合中任意两个节点之间没有边相连。最大独立集的节点数等于节点总数减去最大匹配边数。
最小路径重复点覆盖：在有向图中，用最少的路径覆盖全部节点，路径可以相交。最小路径重复点覆盖数等于最大独立集的节点数。
10. LCA（最近公共先人）
向上标记法
向上标记法的基本思想是先从节点 a 开始，将其到根节点的路径上的全部节点标记，然后从节点 b 开始向上遍历，第一个碰到的已标记节点就是 a 和 b 的最近公共先人。
代码：
#include <iostream>#include <vector>using namespace std;
const int MAXN = 10005;
vector<int> adj;bool vis;int parent;
void dfs(int u, int p) {
parent = p;
for (int v : adj) {
if (v != p) {
dfs(v, u);
}
}}
int lca(int a, int b) {
// 标记 a 到根节点的路径
while (a) {
vis = true;
a = parent;
}
// 从 b 开始向上遍历，找到第一个已标记的节点
while (b) {
if (vis) {
return b;
}
b = parent;
}
return -1;}
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
adj.push_back(v);
adj.push_back(u);
}
dfs(1, 0);
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
fill(vis, vis + MAXN, false);
int anc = lca(a, b);
cout << "The LCA of " << a << " and " << b << " is: " << anc << endl;
}
return 0;}
倍增算法
倍增算法通过预处理一个二维数组 f 表现节点 u 向上跳 2i 步到达的节点，然后利用二进制拆分的思想，快速找到两个节点的最近公共先人。
代码：
#include <bits/stdc++.h>using namespace std;const int N = 40010, M = 17;int n, m;
unordered_map<int, vector<int>> e;int f = {0};int root = 0;int dis;
// 预处理数组void bz() {
memset(dis, 0x3f, sizeof dis);
dis = 0;
dis = 1;
queue<int> q;
q.push(root);
while (q.size()) {
int u = q.front();
q.pop();
for (int v : e) {
if (dis > dis) {
dis = dis + 1;
q.push(v);
f = u;
for (int i = 1; i <= 15; i++) {
f = f];
}
}
}
}}
int get(int x, int y) {
if (dis < dis) swap(x, y);
for (int i = 15; i >= 0; i--) {
if (dis] >= dis) {
x = f;
}
}
if (x == y) return x;
for (int k = 15; k >= 0; k--) {
if (f != f) {
x = f;
y = f;
}
}
return f;}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
int a, b;
scanf("%d%d", &a, &b);
if (b == -1) root = a;
else {
e.push_back(b);
e.push_back(a);
}
}
bz();
cin >> m;
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d%d", &u, &v);
int anc = get(u, v);
if (anc == u) cout << 1 << endl;
else if (anc == v) cout << 2 << endl;
else cout << 0 << endl;
}
return 0;}
Tarjan 算法
初始化：
对给定的树举行预处理，将每个节点的初始状态设置为未遍历（状态 3），并查集的每个元素的父节点初始化为自身，代表每个节点初始时属于独立的集合。
纪录全部需要查询最近公共先人的节点对，以便后续处理。
深度优先搜索：
从树的根节点开始举行深度优先搜索。
当访问到一个节点时，将其状态设置为已遍历但子节点未回溯完（状态 2），即该节点已进入体系栈。
按照从左到右的顺序递归遍历该节点的全部子节点。在递归返回后，说明该子节点的子树已经全部遍历完毕，将该子节点的状态设置为已遍历且子节点全部回溯完（状态 1），同时将子节点所在的并查集归并到当前节点所在的并查集（即将子节点的并查集代表元素设置为当前节点）。
对于每个与当前节点相关的查询对(u,v)或(v,u)：
如果u搜索到v已经处于状态 1（即已遍历且子节点全部回溯完），则通过并查集查找u或v所在集合的代表元素，这个代表元素就是u和v的最近公共先人。因为此时它们在体系栈中的共同先人节点，通过并查集的归并操作，已经成为了它们所在集合的代表元素。
将找到的最近公共先人纪录下来，用于后续输出或其他处理。
输出结果：
遍历全部的查询对，根据纪录的最近公共先人信息，输出每对节点的最近公共先人。
代码：
#include <iostream>#include <vector>#include <utility>using namespace std;
const int MAXN = 10005;
vector<pair<int, int>> adj;
vector<pair<int, int>> query;int res;int n, m;int p;int st;int dep;
int find(int x) {
if (x != p) p = find(p);
return p;}
void tarjan(int u) {
st = 2;
for (auto : adj) {
if (!st) {
dep = dep + 1;
p = u;
tarjan(v);
}
}
int pu = find(u);
for (auto : query) {
if (st == 1) {
res = dep + dep - 2 * dep;
}
}
st = 1;}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
p = i;
}
for (int i = 0; i < n - 1; i++) {
int u, v, w;
cin >> u >> v >> w;
adj.emplace_back(v, w);
adj.emplace_back(u, w);
}
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
query.emplace_back(v, i);
query.emplace_back(u, i);
}
tarjan(1);
for (int i = 0; i < m; i++) {
cout << "The distance between the LCA of query " << i + 1 << " is: " << res << endl;
}
return 0;}
11. 拓扑排序
Kahn 算法
Kahn 算法的基本思想是不绝选择入度为 0 的节点，并将其从图中删除，同时更新其毗邻节点的入度。
代码：
#include <iostream>#include <vector>#include <queue>using namespace std;
vector<int> topologicalSort(int n, vector<vector<int>>& graph) {
vector<int> inDegree(n, 0);
vector<int> result;
queue<int> q;
for (int i = 0; i < n; ++i) {
for (int neighbor : graph) {
++inDegree;
}
}
for (int i = 0; i < n; ++i) {
if (inDegree == 0) {
q.push(i);
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
result.push_back(u);
for (int v : graph) {
--inDegree;
if (inDegree == 0) {
q.push(v);
}
}
}
if (result.size() != n) {
return {};
}
return result;}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> graph(n);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
graph.push_back(v);
}
vector<int> topo = topologicalSort(n, graph);
if (topo.empty()) {
cout << "The graph contains a cycle." << endl;
} else {
for (int node : topo) {
cout << node << " ";
}
cout << endl;
}
return 0;}
12. 欧拉路径和欧拉回路
概念
有向图中：
欧拉路径：
定义：在有向图中，从一个极点出发，经过每条边恰好一次，并且遍历全部极点的路径称为有向图的欧拉路径。
特性：有向图存在欧拉路径，当且仅当该图是连通的，且除了两个极点外，其余极点的入度等于出度。这两个特别极点中，一个极点的入度比出度大 1（终点），另一个极点的出度比入度大 1（起点）。如果全部点的入度和出度数都是相当的也可以。
欧拉回路：
定义：在有向图中，从一个极点出发，经过每条边恰好一次，最后回到起始极点的路径称为有向图的欧拉回路。
特性：有向图存在欧拉回路，当且仅当该图是连通的，且全部极点的入度等于出度。
无向图中：
欧拉路径：
定义：在无向图中，从一个极点出发，经过每条边恰好一次，并且遍历全部极点的路径称为无向图的欧拉路径。
特性：无向图存在欧拉路径，当且仅当该图是连通的，且图中奇度极点（度数为奇数的极点）的个数为 0 或 2。若奇度极点个数为 0，则可以从任意极点出发；若奇度极点个数为 2，则必须从其中一个奇度极点出发，到另一个奇度极点结束。
欧拉回路：
定义：在无向图中，从一个极点出发，经过每条边恰好一次，最后回到起始极点的路径称为无向图的欧拉回路。
特性：无向图存在欧拉回路，当且仅当该图是连通的，且全部极点的度数均为偶数。
有向图的欧拉路径
代码：
#include <bits/stdc++.h>using namespace std;const int N = 100005;
vector<int> g;int in;int out;int s;int top = 0;
void dfs(int u) {
while (!g.empty()) {
int v = g.back();
g.pop_back();
dfs(v);
}
s[++top] = u;}
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
g.push_back(v);
in++;
out++;
}
for (int i = 1; i <= n; i++) {
sort(g.begin(), g.end(), greater<int>());
}
int start = 1;
int cnt = 0;
bool flag = true;
for (int i = 1; i <= n; i++) {
if (out - in == 1) {
start = i;
cnt++;
} else if (out - in == -1) {
cnt++;
} else if (out != in) {
flag = false;
break;
}
}
if (cnt != 0 && cnt != 2) {
flag = false;
}
if (!flag) {
cout << "No" << endl;
} else {
dfs(start);
while (top) {
cout << s;
if (top) {
cout << " ";
}
}
cout << endl;
}
return 0;}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]