当前位置 博文首页 > ACM败犬的博客：Codeforce 1243 D. 0-1 MST（补图搜索，MST，bfs
题意转化为求 由边权为0的边连通的图的连通块的数量 c n t cnt cnt，答案为 c n t ? 1 cnt - 1 cnt?1
用一个 set 维护 所有还没被访问过的点，然后用 bfs 算法对这个图进行遍历，每次遍历一个连通块，把遍历到的点删掉。
最差每一次遍历都会使得 set 的大小减一，复杂度是均摊的
O
(
n
log
?
n
+
n
log
?
m
)
O(n\log n + n\log m)
O(nlogn+nlogm)
(set在删除时,it必须指向下一个，否则 it++会指向其它地方)
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
int n,m;
set<int> g[maxn],st;
int vis[maxn];
void bfs(int x) {
queue<int> q;
st.erase(x);
q.push(x);
while(!q.empty()) {
int top = q.front();
q.pop();
vis[top] = 1;
for(auto it = st.begin(); it != st.end();) {
int v = *it++;
if(g[v].count(top) == 0) {
st.erase(v);
q.push(v);
}
}
}
}
int main() {
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++)
st.insert(i);
for(int i = 1; i <= m; i++) {
int x,y;scanf("%d%d",&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);
}
}
printf("%d\n",cnt - 1);
return 0;
}
