跳转至

环计数问题

普通环计数

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

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

结点数目 。

解题思路

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

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

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

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

三元环计数

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

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

该图没有环的证明

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

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

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

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

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

时间复杂度证明

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

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

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

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

总时间复杂度为 。

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

示例代码（洛谷 P1989 无向图三元环计数） 
#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;
}

例题 2

HDU 6184 Counting Stars

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

，。

解题思路

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

时间复杂度 。

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

四元环计数

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

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

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

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

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

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

示例代码（LibreOJ P191 无向图四元环计数） 
#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;
}

例题 3

Gym 102028L Connected Subgraphs

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

，。

解题思路

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

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

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

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

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

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

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

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

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

习题

洛谷 P3547 [POI2013] CEN-Price List

CodeForces 985G Team Players（容斥原理）

最后更新: 2024年3月26日
创建日期: 2023年9月22日
回到页面顶部