【图论】环问题（最小环、最大环、环计数）-大话世界杯-世界杯德国巴西7比1_国足世界杯

最小环有向带权图最小环算法例题

无向带权图最小环算法例题

无权图最小环算法例题

最大环无权图最大环算法例题

环计数三元环计数算法例题

四元环计数算法例题

最小环

有向带权图最小环

这里不考虑自环，若存在自环，答案与所有自环取最小值即可。

算法

解法一：dijkstra枚举边，复杂度

(

)

O(M(N+M)logN)

O(M(N+M)logN)。对环上一条有向边

→

v \rightarrow u

v→u，从

u 到

v 的最短路

d 加上边长

w 就是包含该边的最小环长，因此枚举所有边即可。一种剪枝优化是可以比较队头与答案大小，若不优显然无需继续跑当前最短路。

解法二：dijkstra枚举顶点，复杂度

(

)

O(N(N+M)logN)

O(N(N+M)logN)，优于前者。当源点

s 的所有邻点都被松弛后，重新将

s 设置为未访问，则

[

]

d[s]

d[s] 就是

s 所在最小环长度。该方法不能在无向图中使用，否则会直接走回源点

s。

例题

2021CCPC桂林站 E. Buy and Delete

题意：一人有代价地选择原图中一些边得到新图，一人在新图中进行若干轮删边操作，每轮所删边集不能含有环。显然新图中有环时必须删两轮，否则一轮删去所有边，若新图无边则无需删除。前者希望后者轮数尽可能多，于是转换为有向图最小环问题。

参考代码（解法一）：

#include

using namespace std;

constexpr int MAXN = 2005;

using PII = pair;

vector G[MAXN];

int d[MAXN], mn = 1e9;

bitset vis;

void dijkstra(int s, int t)

{

memset(d, 0x3f, sizeof(d));

d[s] = 0;

vis.reset();

priority_queue, greater> q;

q.emplace(0, s);

while (!q.empty())

{

int v = q.top().second;

q.pop();

if (d[v] >= mn || v == t)

break;

if (vis[v])

continue;

vis[v] = 1;

for (auto [w, u] : G[v])

{

if (!vis[u] && d[v] + w < d[u])

{

d[u] = d[v] + w;

q.emplace(d[u], u);

}

int main()

{

ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

int n, m, c, ans = 0;

cin >> n >> m >> c;

for (int i = 1; i <= m; i++)

{

int x, y, w;

cin >> x >> y >> w;

G[x].emplace_back(w, y);

if (w <= c)

ans = 1;

}

if (ans == 0)

{

cout << "0\n";

return 0;

}

for (int v = 1; v <= n; v++)

{

for (auto [w, u] : G[v])

{

dijkstra(u, v);

mn = min(mn, d[v] + w);

}

if (mn <= c)

ans = 2;

cout << ans << endl;

return 0;

}

参考代码（解法二）：

#include

using namespace std;

constexpr int MAXN = 2005;

using PII = pair;

vector G[MAXN];

int d[MAXN];

bitset vis;

void dijkstra(int s)

{

memset(d, 0x3f, sizeof(d));

d[s] = 0;

vis.reset();

int flg = 1;

priority_queue, greater> q;

q.emplace(0, s);

while (!q.empty())

{

int v = q.top().second;

q.pop();

if (!flg && v == s)

break;

if (vis[v])

continue;

vis[v] = 1;

for (auto [w, u] : G[v])

{

if (!vis[u] && d[v] + w < d[u])

{

d[u] = d[v] + w;

q.emplace(d[u], u);

}

if (flg)

{

vis[s] = 0, d[s] = 0x3f3f3f3f;

flg = 0;

}

int main()

{

ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

int n, m, c, ans = 0;

cin >> n >> m >> c;

for (int i = 1; i <= m; i++)

{

int x, y, w;

cin >> x >> y >> w;

if (w <= c)

G[x].emplace_back(w, y), ans = 1;

}

if (ans == 0)

{

cout << "0\n";

return 0;

}

int mn = 0x3f3f3f3f;

for (int v = 1; v <= n; v++)

{

dijkstra(v);

mn = min(mn, d[v]);

}

if (mn <= c)

ans = 2;

cout << ans << endl;

return 0;

}

无向带权图最小环

算法

解法一：dijkstra枚举边，复杂度

(

)

O(M(N+M)logN)

O(M(N+M)logN)。注意在无向图中是双向边，必须屏蔽反边，否则会直接走回前一个点。这可以通过成对建边，并屏蔽反边编号来做到。此外，当我们走过一条边之后，无需再走它的反边，这可以保证复杂度不会因为双向边而增大，是非常重要的。

解法二：floyd，复杂度

(

)

O(N^3)

O(N3)。最经典的解法，在大部分情况下都适用。

例题

无向图的最小环问题

题意：求无向图中至少有3个点的最小环长度。这就意味着如果使用dijkstra，不仅要屏蔽反边，还要屏蔽所有与反边平行的重边，也就是说，对于当前枚举边

→

v \rightarrow u

v→u，进行dijkstra处在起点

u 时，无论如何不能走回

v。

参考代码（dijkstra）：

#include

using namespace std;

constexpr int MAXN = 2005, MAXM = MAXN << 3;

int head[MAXN], tot = 1;

struct Edge

{

int to, next, w;

} e[MAXM];

void add(int u, int v, int w)

{

e[++tot].to = v, e[tot].w = w, e[tot].next = head[u];

head[u] = tot;

}

using PII = pair;

int d[MAXN], mn = 0x3f3f3f3f;

bool used[MAXM];

bitset vis;

void dijkstra(int s, int t)

{

memset(d, 0x3f, sizeof(d));

d[s] = 0;

vis.reset();

priority_queue, greater> q;

q.emplace(0, s);

while (!q.empty())

{

int v = q.top().second;

q.pop();

if (d[v] >= mn || v == t)

break;

if (vis[v])

continue;

vis[v] = 1;

for (int i = head[v]; i; i = e[i].next)

{

int u = e[i].to, w = e[i].w;

if (v == s && u == t)

continue;

if (!vis[u] && d[v] + w < d[u])

{

d[u] = d[v] + w;

q.emplace(d[u], u);

}

int main()

{

ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

int n, m;

cin >> n >> m;

for (int i = 1; i <= m; i++)

{

int x, y, w;

cin >> x >> y >> w;

add(x, y, w), add(y, x, w);

}

for (int v = 1; v <= n; v++)

{

for (int i = head[v]; i; i = e[i].next)

{

if (used[i])

continue;

int u = e[i].to, w = e[i].w;

dijkstra(u, v);

mn = min(mn, d[v] + w);

used[i] = used[i ^ 1] = 1;

}

if (mn == 0x3f3f3f3f)

cout << "No solution." << endl;

else

cout << mn << endl;

return 0;

}

参考代码（floyd）：

#include

using namespace std;

constexpr int MAXN = 105, INF = 0x3f3f3f3f;

int n, m, d[MAXN][MAXN], a[MAXN][MAXN], ans = INF;

void floyd()

{

for (int k = 1; k <= n; k++)

{

for (int i = 1; i < k; i++)

for (int j = i + 1; j < k; j++)

if (a[i][k] != INF && a[k][j] != INF && d[i][j] + a[j][k] + a[k][i] < ans)

ans = d[i][j] + a[j][k] + a[k][i];

for (int i = 1; i <= n; i++)

for (int j = 1; j <= n; j++)

if (d[i][k] + d[k][j] < d[i][j])

d[i][j] = d[i][k] + d[k][j];

}

int main()

{

ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

memset(a, 0x3f, sizeof(a));

cin >> n >> m;

for (int i = 1; i <= n; i++)

a[i][i] = 0;

int x, y, w;

for (int i = 1; i <= m; i++)

cin >> x >> y >> w, a[y][x] = a[x][y] = min(a[x][y], w);

memcpy(d, a, sizeof(a));

floyd();

if (ans == INF)

cout << "No solution.\n";

else

cout << ans << endl;

return 0;

}

无权图最小环

算法

上述所有做法都可对应使用，其中dijkstra不需要堆，复杂度降掉一个log，变为普通bfs。

例题

LeetCode.2608 图中的最小环

不需要参考代码了吧

Codeforces Round 869 (Div.1) B. Fish Graph

题意：找到一个环，环上有一个点能够往环外岔出两条边。

思路：枚举度数不小于4的点作为环点，跑bfs求最小环，若有，答案加入另外两条边即可。

参考代码：

#include

using namespace std;

constexpr int MAXN = 2e3 + 5;

int pre[MAXN], deg[MAXN];

vector G[MAXN];

bitset vis;

int bfs(int s, int t)

{

memset(pre, 0, sizeof(pre));

vis.reset();

queue> q;

q.emplace(s, 0);

while (!q.empty())

{

auto [v, p] = q.front();

q.pop();

if (vis[v])

continue;

vis[v] = 1, pre[v] = p;

if (v == t)

return t;

for (auto u : G[v])

if (!vis[u] && !(v == s && u == t))

q.emplace(u, v);

}

return 0;

}

int main()

{

ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

int t;

cin >> t;

while (t--)

{

int n, m;

cin >> n >> m;

while (m--)

{

int v, u;

cin >> v >> u;

G[v].push_back(u), G[u].push_back(v), ++deg[v], ++deg[u];

}

int u = 0;

for (int i = 1; i <= n && !u; i++)

{

if (deg[i] < 4)

continue;

for (auto v : G[i])

if (u = bfs(v, i))

break;

}

if (!u)

cout << "NO\n";

else

{

cout << "YES\n";

int v = u;

vector> e;

while (pre[v])

{

e.emplace_back(v, pre[v]);

v = pre[v];

}

e.emplace_back(v, u);

int cnt = 0;

for (auto w : G[u])

{

if (w != pre[u] && w != v)

e.emplace_back(u, w), ++cnt;

if (cnt == 2)

break;

}

cout << e.size() << "\n";

for (auto [v, u] : e)

cout << v << " " << u << "\n";

}

for (int i = 1; i <= n; i++)

G[i].clear(), deg[i] = 0;

}

return 0;

}

最大环

无权图最大环

算法

如果图没有特殊性质，则这个问题是NPC的（最坏情况下是一个哈密顿环），需要通过dfs暴力枚举所有路径找到答案。若每个点的出度最多为1，说明没有环嵌套的情况，这时图中每个大小不为1的强连通分量都是一个环，使用tarjan算法求出强连通分量即可找到最大环，同样也可求最小环。当然也可以跑拓扑排序把所有的非环边去除，再枚举所有环。

例题

LeetCode.2360 图中的最长环

不需要参考代码了吧

环计数

通常而言，环计数是针对简单无向图而言，没有重边和自环对于简单有向图，可以依然按无向图方法操作，再判断所需的边是否在原图中存在

三元环计数

算法

解法一：根号分治，复杂度

M\sqrt{M}

。根据根号分治的规则，将无向图按照以下方法变为有向图：

边由度数大的点指向度数小的点若度数相等，边由编号小的点指向编号大的点

这之后，所得的有向图是无环的，三元环

(

)

(u,v,w)

(u,v,w) 在新图中的边一定是：

→

u \rightarrow v,v \rightarrow w,u \rightarrow w

u→v,v→w,u→w。我们可以标记

u 的所有出点，再遍历它们，如果出点

v 能到达标记点

w，则找到一个环。

解法二：bitset优化枚举，复杂度

(

)

O(\cfrac{NM}{w})

O(wNM)，稠密图中优于根号分治。对点

v，设其出点集合为

[

]

out[v]

out[v]，入点集合为

[

]

in[v]

in[v]，在无向图情况下

[

]

[

]

out[v]==in[v]

out[v]==in[v]。枚举所有边

→

v \rightarrow u

v→u，则

[

]

∩

[

]

in[v] \cap out[u]

in[v]∩out[u] 就是可能的第三个环点构成的集合，暴力求交集是

(

)

O(N)

O(N) 的，使用bitset优化。注意，所得的最终结果是答案的3倍，因为一个环被每条边计算了三次。

例题

无向图三元环计数

参考代码：

#include

using namespace std;

constexpr int MAXN = 1e5 + 5;

int deg[MAXN], vis[MAXN];

vector G[MAXN];

int main()

{

ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

int n, m;

cin >> n >> m;

vector> e(m);

for (auto &[v, u] : e)

cin >> v >> u, ++deg[v], ++deg[u];

for (auto [v, u] : e)

{

if (deg[v] < deg[u] || deg[v] == deg[u] && v > u)

swap(v, u);

G[v].push_back(u);

}

int ans = 0;

for (int i = 1; i <= n; i++)

{

for (auto u : G[i])

vis[u] = i;

for (auto u : G[i])

for (auto w : G[u])

ans += (vis[w] == i);

}

cout << ans << endl;

return 0;

}

Gym - 100342J Triatrip

参考代码：

#include

using namespace std;

constexpr int MAXN = 1505;

bitset out[MAXN], in[MAXN];

int main()

{

ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

freopen("triatrip.in", "r", stdin);

freopen("triatrip.out", "w", stdout);

int n;

cin >> n;

for (int i = 1; i <= n; i++)

{

string s;

cin >> s;

for (int j = 1; j <= n; j++)

if (s[j - 1] == '+')

out[i][j] = 1, in[j][i] = 1;

}

int64_t ans = 0;

for (int i = 1; i <= n; i++)

for (int j = 1; j <= n; j++)

if (out[i][j])

ans += (out[j] & in[i]).count();

cout << ans / 3 << endl;

return 0;

}

HDU - 6184 Counting Stars

题意：求出共用一条边的三元环个数。

思路：每当找到一个环时，给环的三条边计数加1。最后遍历所有边，如果该边计数大于1，则对答案贡献为

C_{cnt}^2

Ccnt2。

参考代码：

#include

using namespace std;

constexpr int MAXN = 1e5 + 5;

int deg[MAXN], vis[MAXN];

vector G[MAXN];

inline pair mk(int x, int y) { return make_pair(min(x, y), max(x, y)); }

int main()

{

ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

int n, m;

while (cin >> n >> m)

{

map, int> mp;

vector> e(m);

for (int i = 0; i < m; i++)

{

int &v = e[i].first, &u = e[i].second;

cin >> v >> u;

++deg[v], ++deg[u];

}

for (int i = 0; i < m; i++)

{

int v = e[i].first, u = e[i].second;

if (deg[v] < deg[u] || deg[v] == deg[u] && v > u)

swap(v, u);

G[v].push_back(u);

}

for (int i = 1; i <= n; i++)

{

for (auto u : G[i])

vis[u] = i;

for (auto u : G[i])

for (auto w : G[u])

if (vis[w] == i)

++mp[mk(i, u)], ++mp[mk(u, w)], ++mp[mk(i, w)];

}

int64_t ans = 0;

for (const auto &p : mp)

if (p.second > 1)

ans += 1ll * p.second * (p.second - 1) / 2;

cout << ans << "\n";

for (int i = 1; i <= n; i++)

G[i].clear(), vis[i] = 0, deg[i] = 0;

}

return 0;

}

四元环计数

算法

沿用根号分治建图，并根据建图规则给每个点分配唯一

rank

rank 排名（度数越大、编号越小越靠前）。原四元环

(

)

(u,v,w,x)

(u,v,w,x) 在有向图中必然存在两条边

→

u \rightarrow v, u \rightarrow x

u→v,u→x。一个四元环唯一的表示为：

−

→

−

→

u-v\rightarrow w,u-x\rightarrow w

u−v→w,u−x→w 且

[

]

[

]

[

]

rank[u]

u，枚举其在原图的出点

v，枚举

v 在有向图的所有出点

w，这其中隐含

[

]

[

]

rank[v]

[

]

[

]

rank[u]

[

]

cnt[w]

cnt[w] 代表

w 上的有效路径数，只要有两条以上，就能成环，因此答案加上

[

]

cnt[w]

cnt[w]，再令

[

]

cnt[w]++

cnt[w]++。每当更换

u 时，所有点计数要清空。

例题

Gym - 104197F F*** 3-Colorable Graphs

题意：给出一个连通二分图，两侧各有

n 个点，共

m 条边。求最少添加多少条边，能使得整张图无法只用3种颜色染色。

思路：如果一张图无法只用3种颜色染色，一定存在如图所示的结构。由于是连通二分图，显然最多只需要添加3条边就能产生所示结构，故答案不超过3。注意到，若图中存在四元环，这是最佳情况，此时只需要添加同侧边，答案为2。于是本题转换为判断图中是否存在四元环，可以直接套用四元环计数。当然因为是判断，也可直接枚举

u，枚举

v，标记

w 颜色为

u，每次判断是否能找到同色的

w 即可。

参考代码：

#include

using namespace std;

constexpr int MAXN = 2e4 + 5;

int deg[MAXN], cnt[MAXN];

vector G[MAXN], T[MAXN];

int main()

{

ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

int n, m;

cin >> n >> m;

while (m--)

{

int v, u;

cin >> v >> u;

G[v].push_back(u), G[u].push_back(v);

++deg[v], ++deg[u];

}

for (int v = 1; v <= n + n; v++)

for (auto u : G[v])

if (deg[v] > deg[u] || (deg[v] == deg[u] && v < u))

T[v].push_back(u);

int ans = 0;

for (int v = 1; v <= n + n; v++)

{

for (auto u : G[v])

for (auto w : T[u])

if (deg[v] > deg[w] || (deg[v] == deg[w] && v < w))

ans += cnt[w]++;

for (auto u : G[v])

for (auto w : T[u])

if (deg[v] > deg[w] || (deg[v] == deg[w] && v < w))

cnt[w] = 0;

}

cout << (ans ? "2\n" : "3\n");

return 0;

}

世界杯德国巴西7比1_国足世界杯 - sy-wuhan56.com

世界杯德国巴西7比1_国足世界杯 - sy-wuhan56.com