Bỏ qua

Đếm chu trình

Đếm số vòng (chu trình) thông thường

Bài mẫu 1: Codeforces Beta Round 11 D. A Simple Task

Cho một đồ thị đơn giản, hãy đếm số vòng đơn giản trong đồ thị. Vòng đơn giản là vòng không có đỉnh hoặc cạnh lặp lại.

Số đỉnh \(1\leq n\leq 19\).

Ý tưởng giải

Sử dụng quy hoạch động trạng thái (Bitmask DP). Gọi \(f(s,i)\) là số đường đi mà tập các đỉnh đã đi qua là \(s\), hiện tại đang ở đỉnh \(i\), và đỉnh đầu tiên là đỉnh nhỏ nhất trong tập \(s\).

Với trạng thái \(f(s,i)\), liệt kê đỉnh tiếp theo \(u\). Nếu \(u\) đã nằm trong \(s\) và là đỉnh nhỏ nhất (tức là về lại điểm xuất phát), cộng \(f(s,i)\) vào đáp án \(A\). Nếu \(u\) chưa nằm trong \(s\), cập nhật \(f(s\cup\{u\},u)\) bằng \(f(s,i)\).

Cách này sẽ đếm cả vòng độ dài \(2\) (tức là cạnh song song), và mỗi vòng độ dài lớn hơn \(2\) sẽ bị đếm hai lần (vì cố định điểm xuất phát, có thể đi hai chiều). Do đó, đáp án là \(\dfrac{A-m}2\), với \(m\) là số cạnh. Độ phức tạp \(O(2^n m)\).

Code mẫu 
 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
#include <iostream>
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() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int u, v;
    cin >> 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];
      }
    }
  cout << (answer - m) / 2 << '\n';
  return 0;
}

Đếm số vòng tam giác (ba đỉnh)

Vòng tam giác là một bộ ba đỉnh \((u, v, w)\) sao cho tồn tại ba cạnh \((u,v)\), \((v,w)\), \((w,u)\). Bài toán đếm số vòng tam giác yêu cầu đếm số lượng các vòng tam giác trong đồ thị.

Đầu tiên, định hướng các cạnh: luôn hướng từ đỉnh có bậc nhỏ hơn sang đỉnh có bậc lớn hơn, nếu bậc bằng nhau thì từ đỉnh có số nhỏ hơn sang đỉnh có số lớn hơn. Khi đó, đồ thị trở thành đồ thị có hướng không chu trình (DAG).

Chứng minh đồ thị không có chu trình

Giả sử tồn tại chu trình, thì bậc các đỉnh trên chu trình phải tăng dần, để tạo thành chu trình thì các đỉnh phải có cùng bậc, nhưng số hiệu đỉnh lại khác nhau, mâu thuẫn.

Thực chất, quy tắc định hướng này tạo ra một quan hệ thứ tự bộ phận (partial order), nên đồ thị định hướng này (tức là Hasse diagram của quan hệ đó) chắc chắn là DAG.

Duyệt từng đỉnh \(u\), với mỗi đỉnh \(v\) mà \(u\) hướng tới, tiếp tục duyệt các đỉnh \(w\) mà \(v\) hướng tới, kiểm tra xem \(u\) có nối với \(w\) không.

Độ phức tạp \(O(m\sqrt m)\).

Chứng minh độ phức tạp

Định hướng các cạnh duyệt hết \(O(n+m)\).

Với mỗi cặp \((v,w)\), số lượng \(u\) không vượt quá bậc vào \(d^-(v)\). Nếu \(d^-(v)\leq\sqrt m\), số \(w\) tối đa \(n\), tổng \(O(n\sqrt m)\). Nếu \(d^-(v) > \sqrt m\), vì \(v\) hướng tới \(w\) nên \(d(v)\leq d(w)\), suy ra \(d(w)>\sqrt m\), mà tổng số cạnh là \(m\), nên số \(w\) như vậy tối đa \(\sqrt m\), tổng \(O(m\sqrt m)\). Tổng hợp lại là \(O(n+m+n\sqrt m+m\sqrt m)=O(m\sqrt m)\).

Nếu định hướng ngược lại (từ bậc lớn sang bậc nhỏ), chỉ cần đổi vai trò \(u,w\), chứng minh vẫn đúng.

Code mẫu (洛谷 P1989 Đếm số vòng tam giác trong đồ thị vô hướng) 
 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 <iostream>
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() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 1; i <= m; i++) cin >> 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;
  }
  cout << total << '\n';
  return 0;
}

Bài mẫu 2

HDU 6184 Counting Stars

Cho một đồ thị vô hướng có \(n\) đỉnh, \(m\) cạnh, hãy đếm số lần xuất hiện của hình dưới đây.

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

Ý tưởng giải

Hình này là hai vòng tam giác chung một cạnh. Đầu tiên đếm số vòng tam giác trên mỗi cạnh, sau đó với mỗi cạnh có \(x\) vòng tam giác đi qua, cộng \(\dbinom x2\) vào đáp án.

Độ phức tạp \(O(m\sqrt m)\).

Code mẫu 
 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 <cstring>
#include <iostream>
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++) cin >> 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;
    cout << total << '\n';
  }
  return 0;
}

Đếm số vòng bốn đỉnh

Tương tự, vòng bốn đỉnh là bốn đỉnh \(a, b, c, d\) sao cho \((a,b)\), \((b,c)\), \((c,d)\), \((d,a)\) đều là cạnh.

Sắp xếp các đỉnh theo bậc tăng dần.

Duyệt đỉnh cuối cùng \(a\) (bậc lớn nhất), với mỗi đỉnh \(c\) có bậc nhỏ hơn \(a\), đếm số đỉnh \(b\) (bậc nhỏ hơn \(a\)) sao cho \((a,b)\), \((b,c)\) đều là cạnh. Với mỗi cặp \(b\) như vậy, chọn hai đỉnh bất kỳ sẽ tạo thành một vòng bốn đỉnh. Đếm số \(b\) chỉ cần duyệt qua các đỉnh \(b\) và \(c\).

Độ phức tạp tương đương đếm vòng tam giác, tức là \(O(m\sqrt m)\) (giả sử \(n,m\) cùng bậc).

Lưu ý: \((a,b,c,d)\) và \((a,c,b,d)\) có thể là hai vòng bốn đỉnh khác nhau.

Ngoài ra, các đỉnh cùng bậc sẽ có thứ tự khác nhau, cần đảm bảo \(a\neq c\).

Code mẫu (LibreOJ P191 Đếm số vòng bốn đỉnh trong đồ thị vô hướng) 
 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
#include <iostream>
#include <vector>
using namespace std;

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

long long total;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int u, v;
    cin >> 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;
  }
  cout << total << '\n';
  return 0;
}

Bài mẫu 3

Gym 102028L Connected Subgraphs

Cho một đồ thị vô hướng có \(n\) đỉnh, \(m\) cạnh, hỏi có bao nhiêu cách chọn bốn cạnh sao cho đồ thị con tạo thành là liên thông.

\(4\leq n\leq 10^5\), \(4\leq m\leq 2\times 10^5\).

Ý tưởng giải

Có năm trường hợp: đồ thị hình hoa (star), vòng bốn đỉnh, vòng tam giác với một đỉnh nối thêm một cạnh, đường bốn đỉnh với một đỉnh nối thêm một cạnh, và đường năm đỉnh.

Đồ thị hình hoa: duyệt từng đỉnh, dùng tổ hợp để đếm.

Vòng bốn đỉnh: dùng thuật toán ở trên.

Vòng tam giác: duyệt từng vòng tam giác \((u,v,w)\), cộng \([d(u)-2]+[d(v)-2]+[d(w)-2]\) vào đáp án.

Trường hợp thứ tư: duyệt từng đỉnh bậc \(2\) là \(x\), duyệt một đỉnh kề \(y\) là đỉnh bậc \(3\), cộng \([d(x)-1]\cdot\dbinom{d(y)-1}2\) vào đáp án. Tuy nhiên, các đỉnh kề của \(y\) có thể trùng với đỉnh kề của \(x\), khi đó sẽ trùng với trường hợp ba. Mỗi trường hợp ba bị đếm hai lần (vì có hai đỉnh bậc \(3\)), nên cần trừ đi hai lần số trường hợp ba.

Trường hợp cuối: duyệt đỉnh giữa \(x\), đáp án cộng $$ \sum_{y\in son_x}\sum_{z\in son_x}[d(y)-1]\cdot[d(z)-1]. $$ Trong đó, có các trường hợp bị đếm trùng: 1. \(y\) trùng \(t\) nhưng \(s\) khác \(z\), trùng với trường hợp ba; 2. \(s\) trùng \(z\) nhưng \(y\) khác \(t\), cũng trùng với trường hợp ba; 3. \(y\) trùng \(t\), \(s\) trùng \(z\), trùng với vòng tam giác; 4. \(s\) trùng \(t\), trùng với vòng bốn đỉnh.

Trường hợp ba có hai đỉnh bậc \(2\) làm \(x\), đúng bằng hai trường hợp trên, nên cần trừ hai lần số trường hợp ba. Với một vòng tam giác, ba đỉnh đều có thể làm \(x\), bị đếm ba lần. Vòng bốn đỉnh bị đếm bốn lần.

Như vậy, đã liệt kê đủ các trường hợp, độ phức tạp \(O(n+m\sqrt m)\).

Code mẫu 
  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
131
132
#include <iostream>
#include <vector>
using namespace std;
constexpr int mod = 1000000007;

constexpr 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;
}

constexpr 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() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int T;
  cin >> T;
  while (T--) {
    ans[5] = ans[1] = ans[2] = ans[4] = ans[3] = -1;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) E[i].clear(), E1[i].clear(), E2[i].clear();
    while (m--) {
      int x, y;
      cin >> 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);
      }
    cout << ((solve5() + solve1() + solve2() + solve4() + solve3()) % mod +
             mod) %
                mod
         << '\n';
  }
  return 0;
}

Bài tập

洛谷 P3547 [POI2013] CEN-Price List

CodeForces 985G Team Players (nguyên lý bao hàm loại trừ)

Last updated on this page:, Update history
Found an error? Want to help improve? Edit this page on GitHub!
Contributors to this page:OI-wiki
All content on this page is provided under the terms of the CC BY-SA 4.0 and SATA license, additional terms may apply