CF1242B 0-1 MST

传送门

• 思路：

(注：此文设题中输入的图为 \(G_1\)，对应的完全图为 \(G_2\)，对应的补图为 \(G_3\))

首先不难想到暴力思路：直接将 \(G_2\) 建出来，跑一遍 MST 即可。

然而这样时间和空间复杂度都是 \(\operatorname{O}(N^2)\) 的，显然无法承受。

但是这道题显然有别的思路，考虑从特殊的边长：\(0\) 和 \(1\) 入手。

题中所给的边长为 \(1\) 的边视为断边，建出 \(G_3\)，不难发现，答案就是补图的连通块数量减 \(1\)。

我们只需要算出连通块的数量即可，可以用并查集处理。

然而边数仍然很多，直接暴力求连通块很容易 TLE/MLE。

这时这个题目巧妙的地方就来了：我们可以将求解拆成两块，再合并答案。

首先发现，在原图 \(G_1\) 中，设点 \(i\) 的度数为 \(deg_i\)，不难发现

\[\sum\limits_{i=1}^n deg_i =2m \]

那么根据抽屉原理，其中度数最小的点度数不超过 \(\frac{2m}{n}\) ，设该点为 \(u\) .

则可以先将 \(G_1\) 中与 \(u\) 没有连边的点和 \(u\) 暴力合并，和 \(u\) 有连边的点存储下来，暴力合并。

其中暴力合并的复杂度为 \(\operatorname{O}(N)\)，则整体的时间复杂度为 \(\operatorname{O}(N+N\times \frac{2m}{N})=\operatorname{O}(N+M)\).

code:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 100005;
const int maxm = 505;
int n,m;
int cnt;
bool g[maxm][maxn];
struct Edge {
	int u,v;
	Edge() {
		u = v = 0;
	}
	Edge(int u,int v):u(u),v(v){}
}E[maxn];
int deg[maxn],minid = 0;
int pre[maxn];
int seq[maxn],tot = 0,pos[maxn];
int find(int x) {
	return x == pre[x] ? x : pre[x] = find(pre[x]);
}
bool vis[maxn];
int main() {
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= m;++ i) {
		int u,v;
		scanf("%d%d",&u,&v);
		E[i] = Edge(u , v);
		++ deg[u];
		++ deg[v];
	}
	minid = 1;
	for(int i = 2;i <= n;++ i)
		if(deg[i] < deg[minid])minid = i;
	for(int i = 1;i <= n;++ i)pre[i] = i;
	for(int i = 1;i <= m;++ i) {
		if(E[i].u == minid)vis[E[i].v] = true;
		if(E[i].v == minid)vis[E[i].u] = true;
	}
	for(int i = 1;i <= n;++ i) {
		if(vis[i])++ tot,seq[tot] = i,pos[i] = tot;
		else pre[i] = minid;
	}
	//Merge part
	for(int i = 1;i <= m;++ i) {
		if(vis[E[i].u])g[pos[E[i].u]][E[i].v] = true;
		if(vis[E[i].v])g[pos[E[i].v]][E[i].u] = true;
	}
	for(int i = 1;i <= tot;++ i) {
		int u = seq[i];
		for(int j = 1;j <= n;++ j) {
			if(g[i][j])continue ;
			int r1 = find(u),r2 = find(j);
			if(r1 == r2)continue ;
			pre[r1] = r2;
			++ cnt;
		}
	}
	printf("%d",tot - cnt);
	return 0;
}

完结撒花✿✿ヽ(°▽°)ノ✿