题解：P15439 [蓝桥杯 2025 国 Python B] 连通块

· · 题解

题目思路

以下是一种不需要链表就能过的方法。

由于数据中的 n 和 m 很大，正向建图可能会超时或者爆空间，所以我们可以建原图的补图，也就是将删除的边建成一张图，然后在这张图上求解喵。

首先遍历图中的每个节点，尝试以该节点为起点进行广搜。设广搜时队列最前面的元素为 u，遍历图中的每一个元素，检查 u 点和该点是否相邻。如果这两点在补图上相邻，那么在原图上就不相邻，选出所有与 u 点在补图上不相邻，也就是在原图上相邻的点，然后加进队列中即可。

那么，如何检查补图上两点是否相邻呢？很容易想到，可以用二分查找。建图时用邻接表存图，将补图上每个点可以到达的点按从小到大排序，查找时就可以用二分查找，降低时间复杂度。

这样，这道题就写完了。

由于在广搜时会访问到很多没必要访问的点，所以当原图的补图就是完全图时，时间复杂度就被卡到了 O(n^2)，显然会超时喵。

我们发现，超时的原因是因为访问了已经访问过的节点。所以，我们可以用一个 set 将未访问的节点存起来，这样就避免了不必要的访问。这样，时间复杂度就被降低到 O(n \log n + m \log m)，可以通过此题了喵。

code

#include<bits/stdc++.h>
using namespace std;
int n,m,u,v,vis[200005],sum;
vector<int>e[200005],part[200005];
queue<int>q;
set<int>unvis;
bool cmp(vector<int>a,vector<int>b)
{
    return a[0]<b[0];
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    for(int i=1;i<=n;i++)
        sort(e[i].begin(),e[i].end()),unvis.insert(i);
    for(int i=1;i<=n;i++)
    {
        if(vis[i])continue;
        while(!q.empty())q.pop();
        q.push(i);
        vis[i]=1;
        unvis.erase(i);
        sum++;
        while(!q.empty())
        {
            int u=q.front();
            q.pop();
            part[sum].push_back(u);
            for(auto it=unvis.begin();it!=unvis.end();)
            {
                int v=*it;
                if(v==u)
                {
                    it++;
                    continue;
                }
                if(!binary_search(e[u].begin(),e[u].end(),v))
                {
                    vis[v]=1;
                    q.push(v);
                    it=unvis.erase(it);
                }
                else it++;
            }
        }
        sort(part[sum].begin(),part[sum].end());
    }
    sort(part+1,part+sum+1,cmp);
    cout<<sum<<endl;
    for(int i=1;i<=sum;i++)
    {
        cout<<part[i].size()<<" ";
        for(auto cur:part[i])
            cout<<cur<<" ";
        cout<<endl;
    }
    return 0;
}