题解 P1989 【【模板】无向图三元环计数】

一扶苏一 · 2020-02-08 12:36:05 · 题解

【P1989】【模板】无向图三元环计数

快来做这个题呀虽然它标号很小但它确实是个刚上传的新题

Description

给定一个 n 个点 m 条边的简单无向图，求其三元环个数。

Limitations

Solution

Subtask 1 有三种做法，分别是枚举三个点 O(n^3)，枚举两条邻边 O(m^2)，枚举一个点及其对边 O(nm)。这里不再赘述。

我们考虑给所有的边一个方向。具体的，如果一条边两个端点的度数不一样，则由度数较小的点连向度数较大的点，否则由编号较小的点连向编号较大的点。不难发现这样的图是有向无环的。注意到原图中的三元环一定与对应有向图中所有形如 <u \rightarrow v>,<u \rightarrow w>,<v \rightarrow w> 的子图一一对应，我们只需要枚举 u 的出边，再枚举 v 的出边，然后检查 w 是不是 u 指向的点即可。

下面证明这个算法的时间复杂度是 O(m \sqrt m)。

首先我们可以在枚举 u 的出边时给其出点打上 u 的时间戳，这样在枚举 v 的出边时即可 O(1) 去判断 w 是不是 u 的出点。

那么考虑对于每一条边 <u \rightarrow v>，它对复杂度造成的贡献是 out_v，因此总复杂度即为 \sum_{i = 1}^m out_{v_i}，其中 v_i 是第 i 条边指向的点，out_v 是点 v 的出度。

考虑分情况讨论。

1. 当 v 在原图（无向图）上的度数不大于 \sqrt m 时，由于新图每个节点的出度不可能大于原图的度数，所以 out_v = O(\sqrt m)。
2. 当 v 在原图上的度数大于 \sqrt m 时，注意到它只能向原图中度数不小于它的点连边，又因为原图中所有的点的度数和为 O(m)，所以原图中度数大于 \sqrt m 的点只有 O(\sqrt m) 个。因此 v 的出边只有 O(\sqrt m) 条，也即 out_v = O(\sqrt m)。

因此所有节点的出度均为 O(\sqrt m)，总复杂度 \sum_{i = 1}^m out_{v_i} = O(m \sqrt m)。

Code

#include <cstdio>
#include <vector>

const int maxn = 200005;

int n, m, ans;
int dgr[maxn], A[maxn], B[maxn], vistime[maxn];
std::vector<int> e[maxn];

int main() {
  qr(n); qr(m);
  for (int i = 1; i <= m; ++i) {
    qr(A[i]); qr(B[i]);
    ++dgr[A[i]]; ++dgr[B[i]];
  }
  for (int u, v; m; --m) {
    u = A[m]; v = B[m];
    if (dgr[u] > dgr[v]) {
      std::swap(u, v);
    } else if ((dgr[u] == dgr[v]) && (u > v)) {
      std::swap(u, v);
    }
    e[u].push_back(v);
  }
  for (int u = 1; u <= n; ++u) {
    for (auto v : e[u]) vistime[v] = u;
    for (auto v : e[u]) {
      for (auto w : e[v]) if (vistime[w] == u) {
        ++ans;
      }
    }
  }
  printf("%d\n", ans);
  return 0;
}