AIOJ

Counting Simple Cycles

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

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

The number of vertices satisfies $1\leq n\leq 19$ .

Solution

Consider a state-compression dynamic programming approach. Let $f(s,i)$ denote the number of paths whose set of visited vertices is $s$ , whose current vertex is $i$ , and whose first vertex is the one with the smallest index in the vertex set $s$ .

For a state $f(s,i)$ , enumerate the next vertex $u$ . If $u$ belongs to $s$ and is the one with the smallest index (that is, the starting vertex), add the answer $A$ by $f(s,i)$ . If $u$ does not belong to $s$ , add $f(s,i)$ to $f(s\cup\{u\},u)$ .

This also counts 2-cycles (that is, parallel edges), and every non-2-cycle is counted twice because, with the starting vertex fixed, it can be traversed in either direction. Thus the answer is $\dfrac{A-m}2$ , where $m$ is the number of edges. The 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$ is an unordered triple $(u,\ v,\ w)$ such that three edges connect $(u,\ v)$ , $(v,\ w)$ , and $(w,\ u)$ , respectively. The triangle-counting problem asks for the total number of triangles in the graph.

First orient every edge. Direct an edge from the lower-degree vertex to the higher-degree vertex; if the degrees are equal, direct it from the lower-indexed vertex to the higher-indexed vertex. The resulting graph is a directed acyclic graph (DAG).

Proof that the graph has no cycles

Suppose, for a contradiction, that a cycle exists. The degrees of vertices along the cycle would have to increase one by one; for a cycle to close, all vertices would therefore have to have the same degree, but their indices must be different, a contradiction.

Thus the oriented graph certainly has no cycle.

In fact, the orientation rule above defines a partial order, so the graph constructed by this rule (that is, the Hasse diagram of that partial order) must be a DAG.

Enumerate $u$ and each vertex to which $u$ points, denoting such a vertex by $v$ , then, from $v$ , enumerate a vertex and call it $w$ , and check whether $u$ is adjacent to $w$ .

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

Proof of the time complexity

For the orientation step, every edge is traversed, so the time complexity is $O(n+m)$ .

For each pair $(v,\ w)$ , the number of possible $u$ is at most the indegree of $v$ , namely $d^-(v)$ .

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

If $d^-(v) > \sqrt m$ , then because $v$ points to $w$ , we have $d(v) \leq d(w)$ , and hence $d(w) > \sqrt m$ . Since the total number of edges is only $m$ , the number of such $w$ is at most $\sqrt m$ , so this part takes $O(m\sqrt m)$ time.

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

In fact, the complexity is also correct if edges are oriented from higher-degree vertices to lower-degree vertices; simply exchange the two vertices $u,\ w$ , and the proof above still applies.

Example code (Luogu P1989, counting triangles in an 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;
}

Problem 2

HDU 6184 Counting Stars

Given an undirected graph with $n$ vertices and $m$ edges, count 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

This shape consists of two triangles sharing an edge. First run the triangle-counting algorithm and count, for each edge, how many triangles contain it. Then enumerate the shared edge. If it belongs to $x$ triangles, its contribution to the answer is $\dbinom x2$ .

The 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 consists of four vertices $a,\ b,\ c,\ d$ such that edges $(a,\ b)$ , $(b,\ c)$ , $(c,\ d)$ , and $(d,\ a)$ all exist.

Consider sorting the vertices, with lower-degree vertices first and higher-degree vertices later.

Enumerate the last vertex $a$ in this order. For every vertex ranked before $a$ , call it $c$ ; count how many vertices rank before $a$ , call them $b$ , and require $(a,\ b)$ and $(b,\ c)$ to be edges. Any two such vertices $b$ form a 4-cycle. The number of $b$ can be found by traversing the neighbors of $b$ and $c$ once.

The enumeration has essentially the same complexity as triangle counting, so the time complexity is also $O(m\sqrt m)$ , assuming $n,\ m$ are of the same order.

Note that $(a,\ b,\ c,\ d)$ and $(a,\ c,\ b,\ d)$ may be two different 4-cycles.

Also, vertices with equal degrees have different ranks, and one must check that $a\neq c$ .

Example code (LibreOJ P191, counting 4-cycles in an 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;
}

Problem 3

Gym 102028L Connected Subgraphs

Given an undirected graph with $n$ vertices and $m$ edges, count the number of cases in which the induced subgraph of four edges is connected.

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

Solution

The cases can be divided into five types: a star, a 4-cycle, a triangle with one additional edge incident to a vertex, a four-vertex path with one additional edge incident to an interior vertex, and a five-vertex path.

A star can be counted directly by enumerating vertex degrees and using combinations. A 4-cycle can be counted by the algorithm above. For the triangle case, enumerate a triangle $(u,\ v,\ w)$ ; its contribution is $[d(u)-2]+[d(v)-2]+[d(w)-2]$ .

Now consider the fourth type. Enumerate a vertex of degree $2$ , call it $x$ , then enumerate one of its adjacent vertices, call it $y$ , as the vertex of degree $3$ . Its contribution is $[d(x)-1]\cdot\dbinom{d(y)-1}2$ . However, neighbors of $y$ may overlap with neighbors of $x$ , in which case the graph is actually of the third type. Each overcounted third-type case is counted twice, because it has two degree- $3$ vertices, so subtract twice the number of third-type cases.

For the last type, first enumerate the middle vertex $x$ . Its contribution is

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

This also contains overcounted cases. Let $y$ have a neighbor $s$ and $z$ have a neighbor $t$ . The overcounted cases are:

$y$ and $t$ coincide, but $s$ and $z$ do not; this is a third-type case;
$s$ and $z$ coincide, but $y$ and $t$ do not; this is also a third-type case;
both $y$ and $t$ , and $s$ and $z$ , coincide; this is a triangle;
$s$ and $t$ coincide; this is a 4-cycle (the second type).

In the third type, the two degree- $2$ vertices serving as $x$ correspond exactly to overcounting cases 1 and 2 above, so subtract twice the number of third-type cases. For a triangle, all its vertices can serve as $x$ , so it is counted $3$ extra times. Similarly, a 4-cycle is counted $4$ extra times.

This gives 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)

Cycle Counting Problems

Counting Simple Cycles

Counting Triangles

Problem 2

Counting 4-Cycles

Problem 3

Exercises