当前位置 博文首页 > __D. 0-1 MST —— 链表优化 BFS_Scar_Halo：Codeforces Round 5
题目链接：点我啊╭(╯^╰)╮
????
n
n
n 个点的完全图
????给出
m
m
m 条边，边权为
1
1
1，
0
≤
m
≤
m
i
n
(
n
(
n
?
1
)
2
,
1
0
5
)
0≤m≤min( \frac{n(n?1)}{2},10^5)
0≤m≤min(2n(n?1)?,105)
????其他边权为
0
0
0
????求最小生成树
????题目转化为求补图的连通块个数
????每次枚举一个未处理的点，进行宽搜
????然后枚举原图上的每一条边，打上标记
????未被标记的点一定与这个枚举点在补图上属于一个连通块
????将这些未标记的点加入队列，进行宽搜
????用链表优化处理点，处理过的点在链表上删除
????时间复杂度：
O
(
n
+
m
)
O(n+m)
O(n+m)
????枚举边的总复杂度为：
O
(
m
)
O(m)
O(m)
????枚举点分为两种情况：
????①：该点未被标记，则加入队列，每个点只入队一次
????②：该点被标记，时间复杂度算在
O
(
m
)
O(m)
O(m) 内
#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
using pii = pair <ll,int>;
const int maxn = 2e5 + 5;
int n, m, ans[maxn], cnt;
int l[maxn], r[maxn];
int vis[maxn], vis2[maxn];
vector <int> g[maxn];
inline void del(int x){
l[r[x]] = l[x];
r[l[x]] = r[x];
}
void bfs(int x){
vis[x] = ans[++cnt] = 1;
queue <int> Q;
Q.push(x); del(x);
while(Q.size()){
int q = Q.front(); Q.pop();
for(auto v : g[q])
if(!vis[v]) vis2[v] = 1;
for(int i=r[0]; i; i=r[i])
if(!vis2[i]) {
Q.push(i);
del(i);
vis[i] = 1;
++ans[cnt];
} else vis2[i] = 0;
}
}
int main() {
scanf("%d%d", &n, &m);
for(int i=1, u, v; i<=m; i++) {
scanf("%d%d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
for(int i=0; i<=n; i++) l[i] = i-1, r[i] = i+1;
r[n] = 0;
for(int i=1; i<=n; i++)
if(!vis[i]) bfs(i);
printf("%d\n", cnt - 1);
}
