【图论】环问题（最小环、最大环、环计数）

关于图论中环的一些常见问题，包括最小环、最大环、环计数

究极省行怪

5601人浏览 · 2023-05-03 16:13:23

究极省行怪 · 2023-05-03 16:13:23 发布

最小环

有向带权图最小环

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

算法

解法一：dijkstra枚举边，复杂度 $O (M (N + M) l o g N)$ 。对环上一条有向边 $\rightarrow u$ ，从 $u$ 到 $v$ 的最短路 $d$ 加上边长 $w$ 就是包含该边的最小环长，因此枚举所有边即可。一种剪枝优化是可以比较队头与答案大小，若不优显然无需继续跑当前最短路。

解法二：dijkstra枚举顶点，复杂度 $O (N (N + M) l o g N)$ ，优于前者。当源点 $s$ 的所有邻点都被松弛后，重新将 $s$ 设置为未访问，则 $d [s]$ 就是 $s$ 所在最小环长度。该方法不能在无向图中使用，否则会直接走回源点 $s$ 。

例题

2021CCPC桂林站 E. Buy and Delete

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

参考代码（解法一）：

#include <bits/stdc++.h>
using namespace std;

constexpr int MAXN = 2005;
using PII = pair<int, int>;
vector<PII> G[MAXN];
int d[MAXN], mn = 1e9;
bitset<MAXN> vis;

void dijkstra(int s, int t)
{
    memset(d, 0x3f, sizeof(d));
    d[s] = 0;
    vis.reset();
    priority_queue<PII, vector<PII>, greater<PII>> 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 <bits/stdc++.h>
using namespace std;

constexpr int MAXN = 2005;
using PII = pair<int, int>;
vector<PII> G[MAXN];
int d[MAXN];
bitset<MAXN> vis;

void dijkstra(int s)
{
    memset(d, 0x3f, sizeof(d));
    d[s] = 0;
    vis.reset();
    int flg = 1;
    priority_queue<PII, vector<PII>, greater<PII>> 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) l o g N)$ 。注意在无向图中是双向边，必须屏蔽反边，否则会直接走回前一个点。这可以通过成对建边，并屏蔽反边编号来做到。此外，当我们走过一条边之后，无需再走它的反边，这可以保证复杂度不会因为双向边而增大，是非常重要的。

解法二：floyd，复杂度 $O(N^3)$ 。最经典的解法，在大部分情况下都适用。

例题

无向图的最小环问题

题意：求无向图中至少有3个点的最小环长度。这就意味着如果使用dijkstra，不仅要屏蔽反边，还要屏蔽所有与反边平行的重边，也就是说，对于当前枚举边 $\rightarrow u$ ，进行dijkstra处在起点 $u$ 时，无论如何不能走回 $v$ 。

参考代码（dijkstra）：

#include <bits/stdc++.h>
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, int>;
int d[MAXN], mn = 0x3f3f3f3f;
bool used[MAXM];
bitset<MAXN> vis;

void dijkstra(int s, int t)
{
    memset(d, 0x3f, sizeof(d));
    d[s] = 0;
    vis.reset();
    priority_queue<PII, vector<PII>, greater<PII>> 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 <bits/stdc++.h>
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 <bits/stdc++.h>
using namespace std;

constexpr int MAXN = 2e3 + 5;
int pre[MAXN], deg[MAXN];
vector<int> G[MAXN];
bitset<MAXN> vis;

int bfs(int s, int t)
{
    memset(pre, 0, sizeof(pre));
    vis.reset();
    queue<pair<int, int>> 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<pair<int, int>> 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)$ 在新图中的边一定是： $\rightarrow v,v \rightarrow w,u \rightarrow w$ 。
我们可以标记 $u$ 的所有出点，再遍历它们，如果出点 $v$ 能到达标记点 $w$ ，则找到一个环。

解法二：bitset优化枚举，复杂度 $O(\cfrac{NM}{w})$ ，稠密图中优于根号分治。对点 $v$ ，设其出点集合为 $o u t [v]$ ，入点集合为 $in [v]$ ，在无向图情况下 $o u t [v] == in [v]$ 。枚举所有边 $\rightarrow u$ ，则 $\cap out[u]$ 就是可能的第三个环点构成的集合，暴力求交集是 $O (N)$ 的，使用bitset优化。注意，所得的最终结果是答案的3倍，因为一个环被每条边计算了三次。

例题

无向图三元环计数

参考代码：

#include <bits/stdc++.h>
using namespace std;

constexpr int MAXN = 1e5 + 5;
int deg[MAXN], vis[MAXN];
vector<int> G[MAXN];

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> 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 <bits/stdc++.h>
using namespace std;

constexpr int MAXN = 1505;
bitset<MAXN> 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$ 。

参考代码：

#include <bits/stdc++.h>
using namespace std;

constexpr int MAXN = 1e5 + 5;
int deg[MAXN], vis[MAXN];
vector<int> G[MAXN];

inline pair<int, int> 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<pair<int, int>, int> mp;
        vector<pair<int, int>> 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;
}

四元环计数

算法

沿用根号分治建图，并根据建图规则给每个点分配唯一 $r ank$ 排名（度数越大、编号越小越靠前）。
原四元环 $(u, v, w, x)$ 在有向图中必然存在两条边 $\rightarrow v, u \rightarrow x$ 。一个四元环唯一的表示为： $u-v\rightarrow w,u-x\rightarrow w$ 且 $r ank [u] < r ank [v] < r ank [w]$ ，这保证一个四元环不被重复计算。
枚举点 $u$ ，枚举其在原图的出点 $v$ ，枚举 $v$ 在有向图的所有出点 $w$ ，这其中隐含 $r ank [v] < r ank [w]$ ，因此现在只需要满足 $r ank [u] < r ank [w]$ ，即为一条有效路径，我们令 $c n t [w]$ 代表 $w$ 上的有效路径数，只要有两条以上，就能成环，因此答案加上 $c n t [w]$ ，再令 $c n t [w] + +$ 。每当更换 $u$ 时，所有点计数要清空。

例题

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

题意：给出一个连通二分图，两侧各有 $n$ 个点，共 $m$ 条边。求最少添加多少条边，能使得整张图无法只用3种颜色染色。

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

参考代码：

#include <bits/stdc++.h>
using namespace std;

constexpr int MAXN = 2e4 + 5;
int deg[MAXN], cnt[MAXN];
vector<int> 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;
}

开放原子开发者工作坊

开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！

更多推荐

一文解决Cellphonedb单细胞互作分析及可视化作图（2）

开放原子开发者工作坊

[工具使用]——时序图与UML类图

开放原子开发者工作坊

CTFHub技能树 Web-SQL注入详解

整数型注入我们输入 1不断尝试发现闭合方式就是 1 ，整数型存在两列order by 2存在两个注入点/?id=-1 union select 8,9爆库，当前数据库为sqli/?id=-1 union select 8,database()爆出所有表名,这里我们需要吧sqli转换为16进制/?id=-1 union select 8,group_concat(table_name) from i