Articles8
Tags2
Categories0

CodeForces图论刷题之路 1-1243D. 0-1 MST

发现自己图论菜的一 所以开始疯狂刷图论题。这是一道看似最小生成树实则是求补图连通块个数的题。

如何求连通块的个数:对每一个节点,如果他没有被讨论过,即vis[i]=0,则对它进行讨论:将那些剩下未讨论的节点逐个遍历,若他们之间没有权值为1的边相连,则说明在补图中他们是连通的,于是将他们归为一个集合,并从未讨论的集合中删除,这样从1到n逐个遍历。复杂度为(n+m)logn,因为看似是先for一遍再在每个i中再for一遍,可由于边也只有1e5条,所以均摊下来复杂度是成立的。

其中 未讨论的集合我放到了set中,已经讨论过就打上vis标记并从v中删除,每一次讨论用dfs将之后能够加入到这个连通块中的点一并加入,这样就不用并查集最后再遍历一遍数个数了。

QAQ。。。。

时间:140ms

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+50;
const int INF = 1e9;
set<int>g[maxn];
set<int>v;
int vis[maxn];
void dfs(int x){
    vis[x]=1;
    vector<int>tmp;
    for(int i:v){
        if(!g[x].count(i)){
            tmp.push_back(i);
        }
    }
    for(int i:tmp){
        v.erase(i);
    }
    for(int i:tmp){
        dfs(i);
    }
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        g[a].insert(b);g[b].insert(a);        
    }
    for(int i=1;i<=n;i++){
        v.insert(i);
    }
    //memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++) vis[i]=0;int ans=0;
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            ans++;
            v.erase(i);
            dfs(i);
        }
    }
    printf("%d\n",ans-1);
}
Author:西瓜喵喵.
Link:https//:ForgGYLH.github.io/2019/11/09/CFGraphs/
版权声明:本文采用 CC BY-NC-SA 3.0 CN 协议进行许可