Luogu P6680

yaosicheng124 / 2024-09-20 / 原文

题目描述

给定一张 $N$ 个点，$M$ 条边的无向简单图。

如果存在 $1\le a<b<c\le N$ 满足存在边 $(a,b),(a,c)$，并且不存在 $(b,c)$，则加入边 $(b,c)$。

求最后的边数。

思路

首先我们可以把边看做从小的连向大的。

通过观察可以发现只有在这种情况下才会建边：

这里红色的边是新加入的。

如果每次我们都对这样的建一个完全图，那么有很多边会被重复加入，所以我们考虑每个点会伸出去多少条边。

可以发现，这里只需要让最靠前的一个儿子建边就行了，也就是这样：

因为在枚举到这个儿子时又会传递给下一个。

所以我们用一个 set 记录连向的结点，然后用启发式合并的方法传递给儿子。

空间复杂度 $O(N+M)$，时间复杂度 $O(N\log^2 M)$。

代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAXN = 100001;

int n, m;
ll ans;
set<int> e[MAXN];

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n >> m;
  for(int i = 1, u, v; i <= m; ++i) {
    cin >> u >> v;
    e[u].insert(v);
  }
  for(int i = 1; i <= n; ++i) {
    ans += e[i].size();
    if(e[i].size()) {
      int x = *e[i].begin();
      e[i].erase(x);
      if(e[i].size() > e[x].size()) {
        swap(e[i], e[x]);
      }
      for(int v : e[i]) {
        e[x].insert(v);
      }
    }
  }
  cout << ans;
  return 0;
}