跳转至

環計數問題

普通環計數

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

給定一個簡單圖，求圖中簡單環的數目。簡單環是指沒有重複頂點或邊的環。

結點數目 \(1\leq n\leq 19\)。

解題思路

考慮狀態壓縮動態規劃。記 \(f(s,i)\) 表示滿足當前經過結點集合為 \(s\)，且現在在結點 \(i\) 上，且第一個結點為結點集合 \(s\) 中 編號最小的那個 的路徑條數。

對於狀態 \(f(s,i)\)，枚舉下一個結點 \(u\)。若 \(u\) 在集合 \(s\) 中且是編號最小的那個（即起點），就將答案 \(A\) 加上 \(f(s,i)\)。若 \(u\) 不在 \(s\) 中，就將 \(f(s,i)\) 加上 \(f(s\cup\{u\},u)\)。

這樣會把二元環（即重邊）也算上，並且每個非二元環會被計算兩次（因為固定起點可以向兩個方向走），所以答案為 \(\dfrac{A-m}2\)，其中 \(m\) 表示邊數。時間複雜度 \(O(2^nm)\)。

示例代碼 
 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;
}

三元環計數

三元環 指的是一個簡單圖 \(G\) 中的一個無序三元組 \((u,\ v,\ w)\) 滿足存在三條邊分別連接 \((u,\ v)\)，\((v,\ w)\) 和 \((w,\ u)\)。而 三元環計數問題 要求計算出圖中所有三元環的數量。

首先給所有邊定向。我們規定從度數小的點指向度數大的點，度數相同就從編號小的點指向編號大的點。那麼此時此圖是一張有向無環圖（DAG）。

該圖沒有環的證明

反證法，假設存在環，那麼環中的點度數一個比一個大，要形成環，所有點的度數必須相等，但是編號必定不同，矛盾。

所以定向後圖肯定不存在環。

事實上，可以根據上述定向規則構造一個 偏序，所以按此規則構造的圖（也即該偏序的 Hasse 圖）一定是一個 DAG。

枚舉 \(u\) 和 \(u\) 指向的點 \(v\)，再在 \(v\) 指向的點中枚舉 \(w\)，檢驗 \(u\) 是否與 \(w\) 相連即可。

這個算法的時間複雜度為 \(O(m\sqrt m)\)。

時間複雜度證明

對於定向部分，遍歷了所有的邊，時間複雜度 \(O(n+m)\)。

對於每一對 \((v,\ w)\)，\(u\) 的數量都不超過 \(v\) 的入度 \(d^-(v)\)。

若 \(d^-(v)\leq\sqrt m\)，由於 \(w\) 的個數至多為 \(n\)，所以這部分時間複雜度為 \(O(n\sqrt m)\)。

若 \(d^-(v) > \sqrt m\)，由於 \(v\) 指向 \(w\)，所以 \(d(v) \leq d(w)\)，得出 \(d(w) > \sqrt m\)，但是總邊數只有 \(m\)，所以這樣的 \(w\) 的個數至多為 \(\sqrt m\)，故時間複雜度為 \(O(m\sqrt m)\)。

總時間複雜度為 \(O(n+m+n\sqrt m+m\sqrt m)=O(m\sqrt m)\)。

事實上，如果定向時從度數大的點指向度數小的點，複雜度也正確，只需要交換 \(u,\ w\) 兩個點，上述證明也成立。

示例代碼（洛谷 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

給定一張有 \(n\) 個點和 \(m\) 條邊的無向圖，求下面圖形的出現次數。

\(2\leq n\leq 10^5\)，\(1\leq m\leq\min\left\{2\times 10^5,\ \dfrac{n(n-1)}2\right\}\)。

解題思路

這個圖形是兩個三元環共用了一條邊形成的。所以我們先跑一遍三元環計數，統計出一條邊上三元環的數量，然後枚舉共用的那條邊，設有 \(x\) 個三元環中有此邊，那麼對答案的貢獻就是 \(\dbinom x2\)。

時間複雜度 \(O(m\sqrt m)\)。

示例代碼 
 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;
}

四元環計數

類似地，四元環 就是指四個點 \(a,\ b,\ c,\ d\) 滿足 \((a,\ b)\)，\((b,\ c)\)，\((c,\ d)\) 和 \((d,\ a)\) 均有邊連接。

考慮先對點進行排序。度數小的排在前面，度數大的排在後面。

考慮枚舉排在最後面的點 \(a\)，此時只需要對於每個比 \(a\) 排名更前的點 \(c\)，都求出有多少個排名比 \(a\) 前的點 \(b\) 滿足 \((a,\ b)\)，\((b,\ c)\) 有邊。然後只需要從這些 \(b\) 中任取兩個都能成為一個四元環。求 \(b\) 的數量只需要遍歷一遍 \(b\) 和 \(c\) 即可。

注意到我們枚舉的複雜度本質上與枚舉三元環等價，所以時間複雜度也是 \(O(m\sqrt m)\)（假設 \(n,\ m\) 同階）。

值得注意的是，\((a,\ b,\ c,\ d)\) 和 \((a,\ c,\ b,\ d)\) 可以是兩個不同的四元環。

另外，度數相同的結點的排名將不相同，並且需要注意判斷 \(a\neq c\)。

示例代碼（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

給定一張有 \(n\) 個點和 \(m\) 條邊的無向圖，求四條邊的導出子圖連通的情況數。

\(4\leq n\leq 10^5\)，\(4\leq m\leq 2\times 10^5\)。

解題思路

容易把情況分為五種：菊花圖、四元環、三元環上一個點連出一條邊、四個點構成的鏈中間一個點連出一條邊以及五個點構成的鏈。

菊花圖直接枚舉點的度數，用組合數解決即可。四元環可以直接按照上述算法求得。三元環部分只需枚舉三元環 \((u,\ v,\ w)\)，那麼對答案的貢獻就是 \([d(u)-2]+[d(v)-2]+[d(w)-2]\)。

下面考慮第四種情況。考慮枚舉度數為 \(2\) 的點 \(x\)，再枚舉與它相鄰的一個結點 \(y\) 作為度數為 \(3\) 的那個點。此時對答案的貢獻為 \([d(x)-1]\cdot\dbinom{d(y)-1}2\)。但是注意到 \(y\) 的相鄰節點可能會和 \(x\) 的相鄰結點重合，此時的圖形等價於第三種情況。但是每種多算的第三種情況都會被多算兩次（因為有兩個度數為 \(3\) 的點），所以應該減去第三種情況數目的兩倍。

對於最後一種情況，先枚舉中間的點 \(x\)，那麼容易發現對答案的貢獻是

\[ \sum_{y\in son_x}\sum_{z\in son_x}[d(y)-1]\cdot[d(z)-1]. \]

同樣地，這其中有多算的部分。設 \(y\) 的相鄰結點為 \(s\)，\(z\) 的相鄰結點為 \(t\)，那麼思考後發現多算的有如下幾種情況：

  1. \(y\) 與 \(t\) 重合，但是 \(s\) 與 \(z\) 不重合時，等價於第三種情況；
  2. \(s\) 與 \(z\) 重合，但是 \(y\) 與 \(t\) 不重合時，同樣等價於第三種情況；
  3. \(y\) 與 \(t\)，\(s\) 與 \(z\) 都重合時，等價於一個三元環；
  4. \(s\) 與 \(t\) 重合時，等價於一個四元環（第二種情況）。

考慮到第三種情況中兩個度數 \(2\) 的點作為 \(x\) 時正好分別對應上述多算情況的 1 和 2，所以要額外減去第三種情況數目的兩倍。對於一個三元環，三個結點都可以作為 \(x\)，多算了 \(3\) 次。同樣的，四元環的情況被多算了 \(4\) 次。

於是我們就得出了所有情況的算法，時間複雜度為 \(O(n+m\sqrt m)\)。

示例代碼 
  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（容斥原理）

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用