【BZOJ 1098】办公楼（补图连通块个数，Bfs）

补图连通块个数这大概是一个套路吧，我之前没有见到过，想了好久都没有想出来QaQ

事实上这个做法本身就是一个朴素算法，但进行巧妙的实现，就可以分析出它的上界不会超过 $O(n + m)$。

接下来介绍一下这个技巧：

很显然一个不在原图中的边一定在补图中出现，如果我们考虑用朴素的$Bfs$求一个图中的连通块个数，对于当前的一个点$x$，枚举它连出去的边进行拓展即可。

如果是求补图中的，那对于当前队首的点$x$，可以枚举其他所有的点，看是否和这个点有连边，没有就拓展。

一个可以的优化就是，一个点在$Bfs$是不会被入队多次，我们可以把它删掉，这样可以优化原先朴素算法在拓展上$O(n)$枚举的复杂度。

至于为什么删掉不会造成问题，我们可以考虑它有可能存在的问题就是某一个点$x$在拓展的时候准备拓展一个已经被删除的点$y$，那可能会造成原本在一个连通块的点分成多个，这种情况下在之前$y$拓展的时候就会先拓展到$x$；至于如果两个点同时被删除时，那它们一定是同一个根，一定是同一个连通块里的。

接下来证明这样优化之后复杂度的上界是$O(n + m)$：

事实上我们进行每一次拓展的时候，一次失败的拓展是因为原图中存在着这条边，而一旦拓展成功，就能删掉一个点。由于每条边做多被访问一次，于是每次拓展就是要么是减少一条边，要么是减少一个点，故$Bfs$的复杂度上界是$O(n + m)$的。

这个题就是一个例子，在此做一个总结：

#include <cstdio>

#include <queue>

#include <algorithm>

using namespace std;

const int N = ;

int n, m;

int fa[N], vis[N];

vector<int> g[N], ans;

int Sk(int x) {

  return fa[x] == x? x : fa[x] = Sk(fa[x]);

}

void Bfs(int s) {

  static queue<int> Q;

  Q.push(s), fa[s] = Sk(s + );

  ans.push_back();

  for (int x; !Q.empty(); ) {

    x = Q.front(), Q.pop();

    for (int v : g[x]) vis[v] = x;

    for (int i = Sk(); i <= n; i = Sk(i + )) {

      if (vis[i] != x) fa[i] = Sk(i + ), Q.push(i), ++ans.back();

    }

  }

}

int main() {

  scanf("%d%d", &n, &m);

  for (int i = , x, y; i <= m; ++i) {

    scanf("%d%d", &x, &y);

    g[x].push_back(y), g[y].push_back(x);

  }

  for (int i = ; i <= n; ++i) fa[i] = i;

  fa[n + ] = n + ;

  for (int i = ; i <= n; i = Sk(i + )) Bfs(i);

  sort(ans.begin(), ans.end());

  printf("%d\n", (int)ans.size());

  for (int i : ans) printf("%d ", i);

  putchar('\n');

  return ;

}

巴特西

【BZOJ 1098】办公楼（补图连通块个数，Bfs）

最新文章

热门文章