跳转至

环计数问题

普通环计数

例题 1：Codeforces Beta Round 11 D. A Simple Task

给定一个简单图，求图中简单环的数目。简单环是指没有重复顶点或边的环。

结点数目 。

解题思路

考虑状态压缩动态规划。记 表示满足当前经过结点集合为 ，且现在在结点 上，且第一个结点为结点集合 中 编号最小的那个 的路径条数。

对于状态 ，枚举下一个结点 。若 在集合 中且是编号最小的那个（即起点），就将答案 加上 。若 不在 中，就将 加上 。

这样会把二元环（即重边）也算上，并且每个非二元环会被计算两次（因为固定起点可以向两个方向走），所以答案为 ，其中 表示边数。时间复杂度 。

示例代码 
 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
#include <bits/stdc++.h>
using namespace std;

int n, m;

struct Edge {
  int to, nxt;
} edge[500];

int cntEdge, head[20];

void addEdge(int u, int v) {
  edge[++cntEdge] = {v, head[u]}, head[u] = cntEdge;
}

long long answer, dp[1 << 19][20];

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    addEdge(u, v);
    addEdge(v, u);
  }
  for (int i = 1; i <= n; i++) dp[1 << i - 1][i] = 1;
  for (int s = 1; s < (1 << n); s++)
    for (int i = 1; i <= n; i++) {
      if (!dp[s][i]) continue;
      for (int j = head[i]; j; j = edge[j].nxt) {
        int u = i, v = edge[j].to;
        if ((s & -s) > (1 << v - 1)) continue;
        if (s & (1 << v - 1)) {
          if ((s & -s) == (1 << v - 1)) answer += dp[s][u];
        } else
          dp[s | (1 << v - 1)][v] += dp[s][u];
      }
    }
  printf("%lld\n", (answer - m) / 2);
  return 0;
}

三元环计数

三元环 指的是一个简单图 中的一个无序三元组 满足存在三条边分别连接 ， 和 。而 三元环计数问题 要求计算出图中所有三元环的数量。

首先给所有边定向。我们规定从度数小的点指向度数大的点，度数相同就从编号小的点指向编号大的点。那么此时此图是一张有向无环图（DAG）。

该图没有环的证明

反证法，假设存在环，那么环中的点度数一个比一个大，要形成环，所有点的度数必须相等，但是编号必定不同，矛盾。

所以定向后图肯定不存在环。

事实上，可以根据上述定向规则构造一个 偏序，所以按此规则构造的图（也即该偏序的 Hasse 图）一定是一个 DAG。

枚举 和 指向的点 ，再在 指向的点中枚举 ，检验 是否与 相连即可。

这个算法的时间复杂度为 。

时间复杂度证明

对于定向部分，遍历了所有的边，时间复杂度 。

对于每一对 ， 的数量都不超过 的入度 。

若 ，由于 的个数至多为 ，所以这部分时间复杂度为 。

若 ，由于 指向 ，所以 ，得出 ，但是总边数只有 ，所以这样的 的个数至多为 ，故时间复杂度为 。

总时间复杂度为 。

事实上，如果定向时从度数大的点指向度数小的点，复杂度也正确，只需要交换 两个点，上述证明也成立。

示例代码（洛谷 P1989 无向图三元环计数） 
 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
#include <bits/stdc++.h>
using namespace std;

int n, m, total;
int deg[200001], u[200001], v[200001];
bool vis[200001];

struct Edge {
  int to, nxt;
} edge[200001];

int cntEdge, head[100001];

void addEdge(int u, int v) {
  edge[++cntEdge] = {v, head[u]}, head[u] = cntEdge;
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++)
    scanf("%d%d", u + i, v + i), deg[u[i]]++, deg[v[i]]++;
  for (int i = 1; i <= m; i++) {
    if ((deg[u[i]] == deg[v[i]] && u[i] > v[i]) || deg[u[i]] < deg[v[i]])
      swap(u[i], v[i]);
    addEdge(u[i], v[i]);
  }
  for (int u = 1; u <= n; u++) {
    for (int i = head[u]; i; i = edge[i].nxt) vis[edge[i].to] = true;
    for (int i = head[u]; i; i = edge[i].nxt) {
      int v = edge[i].to;
      for (int j = head[v]; j; j = edge[j].nxt) {
        int w = edge[j].to;
        if (vis[w]) total++;
      }
    }
    for (int i = head[u]; i; i = edge[i].nxt) vis[edge[i].to] = false;
  }
  printf("%d\n", total);
  return 0;
}

例题 2

HDU 6184 Counting Stars

给定一张有 个点和 条边的无向图，求下面图形的出现次数。

，。

解题思路

这个图形是两个三元环共用了一条边形成的。所以我们先跑一遍三元环计数，统计出一条边上三元环的数量，然后枚举共用的那条边，设有 个三元环中有此边，那么对答案的贡献就是 。

时间复杂度 。

示例代码 
 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
#include <bits/stdc++.h>
using namespace std;

int n, m, total;
int deg[200001], u[200001], v[200001];
int edgeId[200001], cnt[200001];

struct Edge {
  int to, nxt;
} edge[200001];

int cntEdge, head[100001];

void addEdge(int u, int v) {
  edge[++cntEdge] = {v, head[u]}, head[u] = cntEdge;
}

int main() {
  while (cin >> n >> m) {
    cntEdge = total = 0;
    memset(deg, 0, sizeof deg);
    memset(head, 0, sizeof head);
    for (int i = 1; i <= m; i++)
      scanf("%d%d", u + i, v + i), deg[u[i]]++, deg[v[i]]++;
    for (int i = 1; i <= m; i++) {
      if ((deg[u[i]] == deg[v[i]] && u[i] > v[i]) || deg[u[i]] < deg[v[i]])
        swap(u[i], v[i]);
      addEdge(u[i], v[i]);
    }

    for (int u = 1; u <= n; u++) {
      for (int i = head[u]; i; i = edge[i].nxt) edgeId[edge[i].to] = i;
      for (int i = head[u]; i; i = edge[i].nxt) {
        int v = edge[i].to;
        for (int j = head[v]; j; j = edge[j].nxt) {
          int w = edge[j].to;
          if (edgeId[w]) cnt[i]++, cnt[j]++, cnt[edgeId[w]]++;
        }
      }
      for (int i = head[u]; i; i = edge[i].nxt) edgeId[edge[i].to] = 0;
    }
    for (int i = 1; i <= m; i++) total += cnt[i] * (cnt[i] - 1) / 2, cnt[i] = 0;
    printf("%d\n", total);
  }
  return 0;
}

四元环计数

类似地，四元环 就是指四个点 满足 ，， 和 均有边连接。

考虑先对点进行排序。度数小的排在前面，度数大的排在后面。

考虑枚举排在最后面的点 ，此时只需要对于每个比 排名更前的点 ，都求出有多少个排名比 前的点 满足 ， 有边。然后只需要从这些 中任取两个都能成为一个四元环。求 的数量只需要遍历一遍 和 即可。

注意到我们枚举的复杂度本质上与枚举三元环等价，所以时间复杂度也是 （假设 同阶）。

值得注意的是， 和 可以是两个不同的四元环。

另外，度数相同的结点的排名将不相同，并且需要注意判断 。

示例代码（LibreOJ P191 无向图四元环计数） 
 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
#include <bits/stdc++.h>
using namespace std;

int n, m, deg[100001], cnt[100001];
vector<int> E[100001], E1[100001];

long long total;

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    E[u].push_back(v);
    E[v].push_back(u);
    deg[u]++, deg[v]++;
  }
  for (int u = 1; u <= n; u++)
    for (int v : E[u])
      if (deg[u] > deg[v] || (deg[u] == deg[v] && u > v)) E1[u].push_back(v);
  for (int a = 1; a <= n; a++) {
    for (int b : E1[a])
      for (int c : E[b]) {
        if (deg[a] < deg[c] || (deg[a] == deg[c] && a <= c)) continue;
        total += cnt[c]++;
      }
    for (int b : E1[a])
      for (int c : E[b]) cnt[c] = 0;
  }
  printf("%lld\n", total);
  return 0;
}

例题 3

Gym 102028L Connected Subgraphs

给定一张有 个点和 条边的无向图，求四条边的导出子图连通的情况数。

，。

解题思路

容易把情况分为五种：菊花图、四元环、三元环上一个点连出一条边、四个点构成的链中间一个点连出一条边以及五个点构成的链。

菊花图直接枚举点的度数，用组合数解决即可。四元环可以直接按照上述算法求得。三元环部分只需枚举三元环 ，那么对答案的贡献就是 。

下面考虑第四种情况。考虑枚举度数为 的点 ，再枚举与它相邻的一个结点 作为度数为 的那个点。此时对答案的贡献为 。但是注意到 的相邻节点可能会和 的相邻结点重合，此时的图形等价于第三种情况。但是每种多算的第三种情况都会被多算两次（因为有两个度数为 的点），所以应该减去第三种情况数目的两倍。

对于最后一种情况，先枚举中间的点 ，那么容易发现对答案的贡献是

同样地，这其中有多算的部分。设 的相邻结点为 ， 的相邻结点为 ，那么思考后发现多算的有如下几种情况：

  1. 与 重合，但是 与 不重合时，等价于第三种情况；
  2. 与 重合，但是 与 不重合时，同样等价于第三种情况；
  3. 与 ， 与 都重合时，等价于一个三元环；
  4. 与 重合时，等价于一个四元环（第二种情况）。

考虑到第三种情况中两个度数 的点作为 时正好分别对应上述多算情况的 1 和 2，所以要额外减去第三种情况数目的两倍。对于一个三元环，三个结点都可以作为 ，多算了 次。同样的，四元环的情况被多算了 次。

于是我们就得出了所有情况的算法，时间复杂度为 。

示例代码 
  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
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;

long long power(long long a, long long n = mod - 2) {
  long long res = 1;
  while (n) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}

const long long power24 = power(24), power2 = power(2);

int n, m;
vector<int> E[100001], E1[100001], E2[100001];
bool vis[100001];
int cnt1[100001], cnt2[100001];

long long solve1();
long long solve2();
long long solve3();
long long solve4();
long long solve5();
long long ans[6];

long long solve1() {
  if (ans[1] != -1) return ans[1];
  ans[1] = 0;
  for (int i = 1; i <= n; i++) {
    int x = E[i].size();
    ans[1] +=
        1ll * x * (x - 1) % mod * (x - 2) % mod * (x - 3) % mod * power24 % mod;
  }
  return ans[1] %= mod;
}

long long solve2() {
  if (ans[2] != -1) return ans[2];
  ans[2] = 0;
  for (int i = 1; i <= n; i++) {
    for (int j : E1[i])
      for (int k : E1[j]) cnt1[k]++;
    for (int j : E2[i])
      for (int k : E1[j])
        if (k != i) cnt2[k]++;
    for (int j : E1[i])
      for (int k : E1[j])
        ans[2] +=
            (1ll * cnt1[k] * (cnt1[k] - 1) / 2 + 1ll * cnt1[k] * cnt2[k]) % mod,
            cnt1[k] = 0;
    for (int j : E2[i])
      for (int k : E1[j])
        if (k != i)
          ans[2] += 1ll * cnt2[k] * (cnt2[k] - 1) / 2 % mod * power2 % mod,
              cnt2[k] = 0;
  }
  return ans[2];
}

long long solve3() {
  if (ans[3] != -1) return ans[3];
  ans[0] = ans[3] = 0;
  for (int i = 1; i <= n; i++) {
    for (int j : E1[i]) vis[j] = true;
    for (int j : E1[i])
      for (int k : E1[j])
        if (vis[k])
          ans[3] =
              (1ll * ans[3] + E[i].size() + E[j].size() + E[k].size() - 6) %
              mod,
          ans[0]++;
    for (int j : E1[i]) vis[j] = false;
  }
  return ans[3];
}

long long solve4() {
  if (ans[4] != -1) return ans[4];
  ans[4] = 0;
  for (int i = 1; i <= n; i++)
    for (int j : E[i])
      (ans[4] += 1ll * (E[j].size() - 1) * (E[j].size() - 2) / 2 *
                 (E[i].size() - 1) % mod) %= mod;
  return ans[4] = (ans[4] - 2 * solve3()) % mod;
}

long long solve5() {
  if (ans[5] != -1) return ans[5];
  ans[5] = 0;
  for (int i = 1; i <= n; i++) {
    long long sum = 0;
    for (int j : E[i]) {
      ans[5] += sum * (E[j].size() - 1) % mod;
      sum += E[j].size() - 1;
    }
  }
  solve3();
  return ans[5] =
             (ans[5] % mod - 2 * solve3() - 4 * solve2() - 3 * ans[0]) % mod;
}

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    ans[5] = ans[1] = ans[2] = ans[4] = ans[3] = -1;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) E[i].clear(), E1[i].clear(), E2[i].clear();
    while (m--) {
      int x, y;
      scanf("%d%d", &x, &y);
      E[x].push_back(y), E[y].push_back(x);
    }
    for (int i = 1; i <= n; i++)
      for (int j : E[i]) {
        if (make_pair(E[i].size(), i) < make_pair(E[j].size(), j))
          E1[i].push_back(j);
        else
          E2[i].push_back(j);
      }
    printf(
        "%lld\n",
        ((solve5() + solve1() + solve2() + solve4() + solve3()) % mod + mod) %
            mod);
  }
  return 0;
}

习题

洛谷 P3547 [POI2013] CEN-Price List

CodeForces 985G Team Players（容斥原理）

本页面最近更新：2024/3/27 06:46:12，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：Enter-tainer, megakite, Molmin, Tiphereth-A, untitledunrevised
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用