笔记 - 无向图连通子图 & 环计数

总结一些简单无向图的连通子图 & 环计数的方法

无向图环计数

例题 - [Codeforces 11D] A Simple Task

Given a simple graph, output the number of simple cycles in it. A simple cycle is a cycle with no repeated vertices or edges

Input

The first line of input contains two integers \(n\) and \(m\) (\(1 \leq n \leq 19, 0 \leq m\)) – respectively the number of vertices and edges of the graph. Each of the subsequent m lines contains two integers \(a\) and \(b\), (\(1 \leq a, b \leq n, a \neq b\)) indicating that vertices \(a\) and \(b\) are connected by an undirected edge. There is no more than one edge connecting any pair of vertices

Output

Output the number of cycles in the given graph

Examples

Input
1
2
3
4
5
6
7
4 6
1 2
1 3
1 4
2 3
2 4
3 4
Output
1
7
Note

The example graph is a clique and contains four cycles of length \(3\) and three cycles of length \(4\)

做法

无向图环计数问题是 NP 的,本题可以利用状压 DP 求解

不考虑自环,令

  • \(f(V(G'),x)\) 为导出子图 \(G'\) 中,点 \(\min V(G')\) 到点 \(x\) 的路径条数 (\(x\in V(G')\))
  • \(g(x,y)\) 为边 \((x,y)\) 的重数

\[ f(V(G'),x)=\sum_{v\in V(G)}f(V(G')\setminus\{x\},y)g(y,x) \]

因为是无向图,我们只需要枚举一下这个最小点然后考虑所有与其关联的边即可,最后答案即为

\[ \frac{1}{2}\sum_{v\in V(G)}\sum_{S\subseteq V(G);\min S=v}\sum_{x\in S\setminus\{v\}}f(S,x)g(v,x) \]

时间复杂度

\[ \begin{aligned} \Theta\left(\sum_{i=1}^{2^n-1}(\operatorname{popcount}(i)-1)^2\right)&=\Theta\left(\sum_{i=0}^n(i-1)^2\binom{n}{i}\right)\\ &=\Theta\left(2^{n-2}(n^2-3n+4)\right)\\ &\implies O\left(n^22^n\right) \end{aligned} \]

参考代码

Show code

Codeforces_11Dview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/*
* @Author: Tifa
* @Description: From <https://github.com/Tiphereth-A/CP-archives>
* !!! ATTENEION: All the context below is licensed under a
* GNU Affero General Public License, Version 3.
* See <https://www.gnu.org/licenses/agpl-3.0.txt>.
*/
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
auto solve([[maybe_unused]] int t_ = 0) -> void {
int n, m;
cin >> n >> m;
vector<vector<bool>> g(n, vector<bool>(n));
vector<vector<i64>> dp(1 << n, vector<i64>(n));
for (int i = 1, u, v; i <= m; ++i) {
cin >> u >> v;
--u;
--v;
g[u][v] = g[v][u] = true;
dp[1 << u | 1 << v][u] = dp[1 << u | 1 << v][v] = 1;
}
i64 ans = 0;
for (int s = 1; s < (1 << n); ++s) {
auto __ = __builtin_ctz(s);
for (int i = __ + 1; i < n; ++i) {
if (!(s & (1 << i))) continue;
for (int j = __ + 1; j < n; ++j)
if ((s & (1 << j)) && g[j][i]) dp[s][i] += dp[s ^ (1 << i)][j];
if (g[__][i] && (s ^ (1 << __) ^ (1 << i))) ans += dp[s][i];
}
}
cout << ans / 2 << '\n';
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int i_ = 0;
solve(i_);
return 0;
}

无向图最小环计数 {pending}

例题 - [Luogu P6175] 无向图的最小环问题

给定一张无向图,求图中一个至少包含 \(3\) 个点的环,环上的节点不重复,并且环上的边的长度之和最小。该问题称为无向图的最小环问题。在本题中,你需要输出最小的环的边权和。若无解,输出 No solution.

输入格式

第一行两个正整数 \(n,m\) 表示点数和边数

接下来 \(m\) 行,每行三个正整数 \(u,v,d\), 表示节点 \(u,v\) 之间有一条长度为 \(d\) 的边

输出格式

输出边权和最小的环的边权和。若无解,输出 No solution.

样例输入 #1

1
2
3
4
5
6
7
8
5 7
1 4 1
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20

样例输出 #1

1
61

提示

样例解释:一种可行的方案: \(1-3-5-2-1\)

对于 \(20\%\) 的数据,\(n,m \leq 10\)

对于 \(60\%\) 的数据,\(m\leq 100\)

对于 \(100\%\) 的数据,\(1\le n\leq 100\), \(1\le m\leq 5\times 10^3\), \(1 \leq d \leq 10^5\)

无解输出包括句号

做法

时间复杂度

参考代码

Show code

简单无向图三元环计数

例题 - [Luogu P1989] 无向图三元环计数

无向图 \(G\) 的三元环指的是一个 \(G\) 的一个子图 \(G_0\), 满足 \(G_0\) 有且仅有三个点 \(u, v, w\), 有且仅有三条边 \(\langle u, v \rangle, \langle v, w \rangle, \langle w, u \rangle\). 两个三元环 \(G_1, G_2\) 不同当且仅当存在一个点 \(u\), 满足 \(u \in G_1\)\(u \notin G_2\)

给定一个 \(n\) 个点 \(m\) 条边的简单无向图,求其三元环个数

输入格式

每个测试点有且仅有一组测试数据

输入的第一行是用一个空格隔开的两个整数,分别代表图的点数 \(n\) 和边数 \(m\)

\(2\) 到第 \((m + 1)\) 行,每行两个用空格隔开的整数 \(u, v\), 代表有一条连接节点 \(u\) 和节点 \(v\) 的边

输出格式

输出一行一个整数,代表该图的三元环个数

样例输入 #1

1
2
3
4
3 3
1 2
2 3
3 1

样例输出 #1

1
1

样例输入 #2

1
2
3
4
5
6
7
8
9
5 8
1 2
2 3
3 5
5 4
4 2
5 2
1 4
3 4

样例输出 #2

1
5

提示

【样例 2 解释】

共有 \(5\) 个三元环,每个三元环包含的点分别是 \(\{1, 2, 4\}, \{2, 3, 4\}, \{2, 3, 5\}, \{2, 4, 5\}, \{3, 4, 5\}\)

【数据规模与约定】

本题采用多测试点捆绑测试,共有两个子任务

  • Subtask 1 (30 points): \(n \le 500\), \(m \le {10}^3\)
  • Subtask 2 (70 points): 无特殊性质

对于 \(100\%\) 的数据,\(1 \le n \le 10^5\), \(1 \le m \le 2 \times {10}^5\), \(1 \le u, v \le n\), 给出的图不存在重边和自环,但不保证图连通

【提示】

  • 请注意常数因子对程序效率造成的影响

做法

我们不难想到三种暴力做法:

  • 枚举三点: \(O(n^3)\)
  • 枚举两边: \(O(m^2)\)
  • 枚举一点和对边: \(O(nm)\)

另外还可以使用 std::vector<std::bitset> 开邻接矩阵来对暴力进行优化,同时和点 \(i\), 点 \(j\) 相邻的点集可以通过两个点对应的 bitset& 得到

若题目卡空间,可以考虑设置一个阈值 \(T\), 将度数不超过 \(T\) 的点直接暴力,度数超过 \(T\) 的点用 bitset 优化

下面我们介绍一种更优的算法,其时间复杂度为 \(O(m\sqrt{m})\), 因为 \(O(n)\leq m\leq O(n^2)\), 所以该算法总体来说是优于上述三种暴力算法的

定义严格弱序 \(\prec\) 满足

\[ u\prec v:=\begin{cases} \deg(u)<\deg(v),&\deg(u)\neq\deg(v)\\ u<v,&\deg(u)=\deg(v) \end{cases} \]

我们对原图 \(G\) 赋方向,若 \((u,v)\in E(G)\)\(u\prec v\), 则将该边改为弧 \(u\to v\) (\(\langle u,v\rangle\))

因为 \(\prec\) 是严格弱序,所以得到的新图 \(G'\) 是 DAG, 并且 \(G\) 的三元环 \(u,v,w\) (顶点按一定顺序排列后) 在 \(G'\) 中与 \(u\to v\), \(u\to w\), \(v\to w\) 一一对应

所以在新图中我们只需要枚举 \(u\), 接着枚举 \(u\) 的邻接点 \(v\), 最后看 \(v\) 的邻接点 \(w\) 是否是 \(u\) 的邻接点即可

时间复杂度

注意到

  • \(v\)\(G\) 中的度数小于 \(\sqrt{m}\), 则在 \(G'\) 中也不可能超过 \(\sqrt{m}\), 所以 \(\deg_{out}(v)=O(\sqrt{m})\)
  • \(v\)\(G\) 中的度数不小于 \(\sqrt{m}\), 由于 \(v\)\(G'\) 中只能向度数不小于自身的点连边,所以 \(\deg_{out}(v)=O(\sqrt{m})\)

故时间复杂度为

\[ \begin{aligned} \Theta\left(\sum_{u\in V(G')}\sum_{\langle u, v\rangle\in E(G')}\deg_{out}(v)\right)&= \Theta\left(\sum_{\langle u, v\rangle\in E(G')}\deg_{out}(v)\right)\\ &\implies O\left(\sum_{\langle u, v\rangle\in E(G')}O\left(\sqrt{m}\right)\right)\\ &= O(m\sqrt{m}) \end{aligned} \]

参考代码

Show code

Luogu_P1989view raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/*
* @Author: Tifa
* @Description: From <https://github.com/Tiphereth-A/CP-archives>
* !!! ATTENEION: All the context below is licensed under a
* GNU Affero General Public License, Version 3.
* See <https://www.gnu.org/licenses/agpl-3.0.txt>.
*/
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
auto solve([[maybe_unused]] int t_ = 0) -> void {
int n, m;
cin >> n >> m;
vector<vector<int>> dg(n + 1);
{
vector<int> deg(n + 1);
vector<pair<int, int>> edges;
edges.reserve(m);
for (int i = 1, u, v; i <= m; ++i) {
cin >> u >> v;
++deg[u];
++deg[v];
edges.emplace_back(u, v);
}
auto __lt__ = [&](int u, int v) -> bool {
return deg[u] < deg[v] || (deg[u] == deg[v] && u < v);
};
for (auto [u, v] : edges) {
if (!__lt__(u, v)) swap(u, v);
dg[u].push_back(v);
}
}
i64 c3 = 0;
vector<int> pre(n + 1);
for (int u = 1; u <= n; ++u) {
for (auto v : dg[u]) pre[v] = u;
for (auto v : dg[u])
for (auto w : dg[v]) c3 += pre[w] == u;
}
cout << c3 << '\n';
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int i_ = 0;
solve(i_);
return 0;
}

简单无向图四元环计数

做法

算法和 简单无向图三元环计数 类似,下面简述流程

建图 \(G'\) 的方式不变,只不过这里的四元环 \(u,v,w,x\)\(G'\) 中可能有以下三种同构形式:

形式 1形式 2形式 3

不难发现这三种形式均可以视作如下形式

所以此时我们需要枚举 \(u\to v-w\), 两条这样的路径即构成一个四元环

时间复杂度

\(O(m\sqrt{m})\)

参考代码

Show code

cntsr4.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
auto solve([[maybe_unused]] int t_ = 0) -> void {
int n, m;
cin >> n >> m;
vector<int> deg(n + 1);
vector<vector<int>> dg(n + 1);
vector<vector<int>> g(n + 1);
auto __lt__ = [&](int u, int v) -> bool {
return deg[u] < deg[v] || (deg[u] == deg[v] && u < v);
};
{
vector<pair<int, int>> edges;
edges.reserve(m);
for (int i = 1, u, v; i <= m; ++i) {
cin >> u >> v;
++deg[u];
++deg[v];
edges.emplace_back(u, v);
}
for (auto [u, v] : edges) {
if (!__lt__(u, v)) swap(u, v);
dg[u].push_back(v);
g[u].push_back(v);
g[v].push_back(u);
}
}
i64 c4 = 0;
vector<int> pre(n + 1), cnt(n + 1);
for (int u = 1; u <= n; ++u)
for (auto &&v : dg[u])
for (auto &&w : g[v]) {
if (u == w || !__lt__(u, w)) continue;
if (pre[w] != u) cnt[w] = 0;
c4 += cnt[w]++;
pre[w] = u;
}
cout << c4 << '\n';
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int i_ = 0;
solve(i_);
return 0;
}

简单无向图含 k 条边的连通子图计数 (k < 5) {pending}

做法

时间复杂度

参考代码

Show code


参考资料