题意

一个 $n$ 个点无向连通完全图,边权只有 $0$ 和 $1$。问最小权值生成树。 指定 $m$ 条边的权值为 $1$,剩下边的权值都为 $0$。

$1 \leq n \leq 10^5$

分析

首先答案是连通块的个数减一。

接下来就是如何求补图连通块的个数。

维护一个队列,队列中的元素都是一个连通块的。

从每个未访问节点出发,将所有相连的节点都打上标记,然后将没有标记且未访问过的节点放入队列中(这些点都在同一个连通块中)。清空标记。继续 $bfs$。

对于那些未访问过的节点,用一个双向链表来维护,每次放入队列时,就从链表中删除相应元素。

复杂度分析:首先每个点只会入队一次。接下来的复杂度主要是在 $bfs$ 时链表的遍历。换个角度考虑,每个点只会被遍历它的度数次。因此最终的复杂度是 $O(|V| + |E|)$。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
vector<int> G[maxn];
bool vis[maxn];
bool used[maxn];
pair<int, int> a[maxn];
 
inline void del(int u) {
  a[a[u].first].second = a[u].second;
  a[a[u].second].first = a[u].first;
}
void bfs(int s) {
  used[s] = true;
  queue<int> q;
  q.push(s);
  while (!q.empty()) {
    auto u = q.front();
    q.pop();
    for (auto &v : G[u]) vis[v] = true;
    for (int v = a[0].second; v; v = a[v].second)
      if (!vis[v] && !used[v]) q.push(v), del(v), used[v] = true;
    for (auto &v : G[u]) vis[v] = false;
  }
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 0, a, b; i < m; i++) {
    scanf("%d%d", &a, &b);
    G[a].push_back(b);
    G[b].push_back(a);
  }
  int cnt = 0;
  for (int i = 1; i <= n; i++) a[i].first = i - 1, a[i].second = i + 1;
  a[0].second = 1;
  a[n].second = 0;
  for (int i = 1; i <= n; i++)
    if (!used[i]) bfs(i), cnt++;
  printf("%d\n", cnt - 1);
}
最后修改:2020 年 07 月 30 日 11 : 23 PM