当前位置 博文首页 > 多一些不为什么的坚持:D. 0-1 MST
题目:D. 0-1 MST
总结 :题目求的就是补图的连通块-1。首先可以把1~n个点都存放到set的s中。当某个点没有被访问过的时候,就调用bfs函数,从s中删除,因为这个点已经访问了,并且加入到队列中。
寻找在补图中和这个点相连的,遍历s,如果找到一个v和k并没有相连,就说明它们是补图中相连的。就从s中删除,加入队列,并且做上标记。
/*求补图的连通块*/
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+5;
set<int>G[N];
int n,m;
set<int>s;
int vis[N];
set<int>::iterator it;
void bfs(int x){
queue<int>q;
s.erase(x);//将在s中的x删掉
q.push(x);//需要连接与x相连的
vis[x] = 1;//表示这个点已经访问过了
while(!q.empty()){
int k = q.front();
q.pop();
for(it = s.begin();it != s.end();){
int v = *it++;//这儿因为下面可能要把这个地址删除,所以先增加。这样删除就不影响了
if(G[v].count(k) == 0){//表示和k相连的并没有v,所以就是补图中的一个
s.erase(v);//因为已经访问过了,以后不需要访问了,所以可以删掉
q.push(v);
vis[v] = 1;
}
}
}
}
int main(){
cin >> n >> m;
for(int i = 1;i <= n;i++){
s.insert(i);
}
while(m--){
int x,y;
cin >> x >> y;
G[x].insert(y);
G[y].insert(x);//代表这个点是原来的图里有了多少的点
}
int cnt = 0;
for(int i = 1;i <= n;i++){
if(!vis[i]){
cnt++;
bfs(i);
}
}
cout<<cnt-1<<endl;
return 0;
}
cs