Cycle Counting

Counting Simple Cycles

Example 1: Codeforces Beta Round 11 D. A Simple Task

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

Number of vertices \(1\leq n\leq 19\).

Solution Idea

Consider state compression dynamic programming. Let \(f(s,i)\) denote the number of paths satisfying that the current set of visited vertices is \(s\), the current vertex is \(i\), and the first vertex is the smallest numbered vertex in the set \(s\).

For state \(f(s,i)\), enumerate the next vertex \(u\). If \(u\) is in set \(s\) and is the smallest numbered vertex (i.e., the starting point), add \(f(s,i)\) to the answer \(A\). If \(u\) is not in \(s\), add \(f(s\cup\{u\},u)\) to \(f(s,i)\).

This will count 2-cycles (i.e., parallel edges) as well, and each non-2-cycle will be counted twice (because fixing the starting point allows traversal in two directions). Thus, the answer is \(\dfrac{A-m}2\), where \(m\) is the number of edges. Time complexity is \(O(2^nm)\).

Example Code

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

Counting Triangles

A triangle in a simple graph \(G\) refers to an unordered triple \((u,\ v,\ w)\) such that there exist edges connecting \((u,\ v)\), \((v,\ w)\), and \((w,\ u)\). The triangle counting problem asks to compute the number of all triangles in the graph.

First, orient all edges. We stipulate that edges go from vertices with smaller degree to vertices with larger degree; if degrees are equal, go from the vertex with smaller index to the vertex with larger index. Then the resulting graph is a directed acyclic graph (DAG).

Proof that this graph has no cycles

Proof by contradiction. Assume a cycle exists. Then the degrees of vertices in the cycle increase one by one. To form a cycle, all vertices must have the same degree, but their indices must differ, leading to a contradiction.

Therefore, after orientation, the graph certainly contains no cycles.

In fact, the above orientation rule can be used to construct a partial order, so the graph constructed by this rule (i.e., the Hasse diagram of this partial order) must be a DAG.

Enumerate \(u\) and the vertices \(v\) pointed to by \(u\), then among the vertices pointed to by \(v\), enumerate \(w\), and check whether \(u\) is connected to \(w\).

The time complexity of this algorithm is \(O(m\sqrt m)\).

Proof of Time Complexity

For the orientation part, all edges are traversed, with time complexity \(O(n+m)\).

For each pair \((v,\ w)\), the number of possible \(u\) does not exceed the in-degree \(d^-(v)\) of \(v\).

If \(d^-(v)\leq\sqrt m\), since the number of \(w\) is at most \(n\), the time complexity for this part is \(O(n\sqrt m)\).

If \(d^-(v) > \sqrt m\), since \(v\) points to \(w\), we have \(d(v) \leq d(w)\), implying \(d(w) > \sqrt m\). However, the total number of edges is only \(m\), so the number of such \(w\) is at most \(\sqrt m\). Hence, the time complexity is \(O(m\sqrt m)\).

The total time complexity is \(O(n+m+n\sqrt m+m\sqrt m)=O(m\sqrt m)\).

In fact, if we orient edges from vertices with larger degree to vertices with smaller degree, the complexity remains correct; we only need to swap the roles of \(u\) and \(w\), and the above proof still holds.

Example Code (Luogu P1989 Counting Triangles in Undirected Graph)

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

Example 2

HDU 6184 Counting Stars

Given an undirected graph with \(n\) vertices and \(m\) edges, find the number of occurrences of the following shape.

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

Solution Idea

This shape is formed by two triangles sharing a common edge. So we first run triangle counting to compute the number of triangles containing each edge. Then, for each shared edge, if there are \(x\) triangles containing it, the contribution to the answer is \(\dbinom x2\).

Time complexity is \(O(m\sqrt m)\).

Example Code

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

Counting 4-Cycles

Similarly, a 4-cycle refers to four vertices \(a,\ b,\ c,\ d\) such that edges exist connecting \((a,\ b)\), \((b,\ c)\), \((c,\ d)\), and \((d,\ a)\).

Consider first sorting the vertices. Vertices with smaller degree come first; vertices with larger degree come later.

Consider enumerating the vertex \(a\) with the largest rank. Now, for each vertex \(c\) with a rank smaller than \(a\), we need to find how many vertices \(b\) with rank smaller than \(a\) satisfy that edges exist connecting \((a,\ b)\) and \((b,\ c)\). Then, any two such \(b\) can form a 4-cycle. The number of such \(b\) can be found by iterating over \(b\) and \(c\).

Note that the complexity of our enumeration is essentially equivalent to enumerating triangles, so the time complexity is also \(O(m\sqrt m)\) (assuming \(n\) and \(m\) are of the same order).

It is worth noting that \((a,\ b,\ c,\ d)\) and \((a,\ c,\ b,\ d)\) can be two different 4-cycles.

Also, vertices with the same degree are assigned different ranks, and we must ensure \(a\neq c\).

Example Code (LibreOJ P191 Counting 4-Cycles in Undirected Graph)

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

Example 3

Gym 102028L Connected Subgraphs

Given an undirected graph with \(n\) vertices and \(m\) edges, find the number of connected subgraphs induced by four edges.

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

Solution Idea

The cases can be divided into five types: star graph, 4-cycle, a triangle with an extra edge attached to one vertex, a chain of four vertices with an extra edge attached to the middle vertex, and a chain of five vertices.

For star graphs, directly enumerate vertex degrees and use combinations. For 4-cycles, directly use the above algorithm. For triangles, enumerate each triangle \((u,\ v,\ w)\); the contribution to the answer is \([d(u)-2]+[d(v)-2]+[d(w)-2]\).

Now consider the fourth case. Enumerate the vertex \(x\) with degree 2, then enumerate one of its neighbors \(y\) as the vertex with degree 3. The contribution to the answer is \([d(x)-1]\cdot\dbinom{d(y)-1}2\). However, note that \(y\)'s neighbors may coincide with \(x\)'s neighbors; this case is equivalent to the third case. But each such overcounted third case is counted twice (because there are two vertices of degree 3), so we should subtract twice the number of third cases.

For the last case, first enumerate the middle vertex \(x\). It is easy to see that the contribution to the answer is

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

Again, there are overcounted parts. Let \(s\) be a neighbor of \(y\), and \(t\) be a neighbor of \(z\). After analysis, the overcounted cases are as follows:

1. When \(y\) coincides with \(t\) but \(s\) does not coincide with \(z\), it is equivalent to the third case;
2. When \(s\) coincides with \(z\) but \(y\) does not coincide with \(t\), it is also equivalent to the third case;
3. When both \(y\) coincides with \(t\) and \(s\) coincides with \(z\), it is equivalent to a triangle;
4. When \(s\) coincides with \(t\), it is equivalent to a 4-cycle (the second case).

Considering that in the third case, the two vertices of degree 2 acting as \(x\) correspond exactly to the overcounted cases 1 and 2 above, we need to subtract twice the number of third cases additionally. For a triangle, all three vertices can act as \(x\), so it is overcounted 3 times. Similarly, a 4-cycle is overcounted 4 times.

Thus, we obtain the algorithm for all cases, with time complexity \(O(n+m\sqrt m)\).

Example Code

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

Exercises

Luogu P3547 [POI2013] CEN-Price List

CodeForces 985G Team Players (Inclusion-Exclusion Principle)

---

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