题解 CF920E 【Connected Components?】

· · 题解

CF920E Connected Components? : 链表优化广度优先搜索。

题目大意：给定一张无向图 G , 求 G 的补图的连通块的个数。

这里补图就是完全图 K 去掉所有 G 中的连边，也就是断掉所有原本连着的两个点，连上所有原本没有连接的两个点。记 G 的补图为 T 。如果点 s 和点 t 处于同一个连通块中，那么一定有一条路径可以从 s 到 t ,所有满足上述条件的 s 和 t 点的集合称为一个连通块。

我们先将所有的边读入进来，假定一开始所有的点都不属于任何一个连通块，然后将所有的点扫一遍，如果发现一个点 s 不属于任何一个连通块，以 s 为起点广度优先搜索，枚举一下点 t ，如果 s 和 t 在 G 中没有连边，就将 t 加入队列中，与此同时记录一下当前连通块的大小。这么做是正确的，除了这个补图有点非同寻常以外几乎与正常地求连通块没有区别，但是，这么做每一次枚举 t 都要尝试所有可能的点，时间复杂度高达 O(N^2)，难以承受。

BFS代码如下，我们可以以这个为模型考虑优化的方案。

int _count(const int &start) {
    queue<int> que; que.push(start);
    vis[start] = true;

    int nowAt, _cnt = 1, i;
    while (!que.empty()) {
        nowAt = que.front(); que.pop();
        sort(G[nowAt].begin(), G[nowAt].end());
        for (int to = i = 0; to < totPoints; to++) {
            if (i < G[nowAt].size() && to == G[nowAt][i]) { i++; continue; }
            if (!vis[to]) { vis[to] = true; que.push(to); _cnt++; }
        }
    }
    return _cnt;
}

时间超出限制的根本原因就是枚举 t 的时候浪费了大量的计算能力，事实上，大部分的 t 都已经属于其它的连通块了，因此永远不可能用得上，能不能不枚举这些点呢？其实是可以的，如果发现了一个 t 可以加入当前的连通块，我们将其删掉就可以了，这可以用一种数据结构在 O(1) 的时间复杂度内完成这一操作。

套上了链表，我们还可以用一个集合 S 保存图 G 中所有的连边，最后判断一下如果 s \to t 这条边不在集合 S 中，说明这是一个合法的 t.

AC代码如下：

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

//链表----------------------------
struct Node {
    int val; Node *nxt;
    void DeleteNext() { 
        if (this->nxt == nullptr)return;
        Node *it = this->nxt; this->nxt = it->nxt;
        it = nullptr;
    }
}*frnt = nullptr;
Node* newNode() {
    Node* ext = (Node*)malloc(sizeof(Node));
    ext->nxt = nullptr; return ext;
}
void build(size_t siz) { //在一开始，所有的点都在链表中
    frnt = newNode(); frnt->val = 0;
    Node *it = frnt, *ext;
    for (int i = 1; i < siz; i++) {
        ext = newNode(); ext->val = i;
        it->nxt = ext; it = ext;
    }
}
//-------------------------------------

#define MAXPOINTS 200005
vector<int> cnt;    //每一个连通块包含的点的个数
int totPoints, totEdges;
bool vis[MAXPOINTS];

struct Edge {
    int fr, to;
    bool operator < (Edge comp) const {
        return fr == comp.fr ? to < comp.to : fr < comp.fr;
    }
};
set<Edge> G;    //图G

int _count(const int &start) {//广搜
    queue<int> que; que.push(start);
    int nowAt, _cnt = 1;

    while (!que.empty()) {
        nowAt = que.front(); que.pop();
        for (Node *it = frnt; it != nullptr && it->nxt != nullptr;) {//我也不知道这里到底循环了多少次
            if (vis[it->nxt->val]) { it->DeleteNext(); continue; }
            if (G.count({ nowAt,it->nxt->val }) || it->nxt->val == nowAt) { it = it->nxt; continue; }
            vis[it->nxt->val] = true; _cnt++;
            que.push(it->nxt->val);
            it->DeleteNext();
        }
    }
    return _cnt;
}

int main()
{
    memset(vis, false, sizeof(vis));
    int a, b;

    cin >> totPoints >> totEdges;
    for (int i = 0; i < totEdges; i++) {
        scanf("%d%d", &a, &b); --a; --b;
        G.insert({ a,b }); G.insert({ b,a });
    }
    build(totPoints);

    for (Node* it = frnt; it != nullptr; it = it->nxt) {
        if (vis[it->val])continue;
        vis[it->val] = true;
        cnt.push_back(_count(it->val));
    }

    cout << cnt.size() << endl;
    sort(cnt.begin(), cnt.end());//输出时要是排好序了的
    for (const auto &it : cnt)
        printf("%d ", it);
    putchar('\n');

    //system("pause");
    return 0;
}

其实，如果去掉链表的部分不看，代码还是非常直观的

有了链表的优化可以将所有枚举将为 N 次，由于每次判断是否在集合中为 O(logN) ，所以时间复杂度为 O(玄学) O(NlogN) ?