Codeforces 1243 D 0-1 MST

隐隐感觉N年前做过一道类似的题。

很显然我们只需要考虑，仅有0边的子图有多少个连通块，然后这个数量减去1就是答案了(这个和kruscal过程等价)。

然后其实就是妥妥的暴力了。。。因为1边数量非常之少，于是我们就可以直接每次暴力合并两个连通块。

显然这里判断是否能合并的总复杂度是 O(M)的，因为不同阶段连通块的判断不会用到同一条边，而只要两个连通块中有一条不是1的边就可合并；

合并的复杂度的话，启发式合并可以做到 O(N log N)。

于是就愉快的做完了，代码还超好写233

#include<bits/stdc++.h>

#define ll long long

using namespace std;

#define pb push_back

const int N=100005;

unordered_map<int,int> mmp[N];

vector<int> g[N];

int n,p[N],m,U,V,sz;

int getfa(int x){ return p[x]==x?x:(p[x]=getfa(p[x]));}

inline bool can(int x,int y){

	for(int i:g[x])

	    for(int j:g[y]) if(!mmp[i][j]) return 1;

	return 0;

}

inline void Merge(int x,int y){

	if(g[x].size()>g[y].size()) swap(g[x],g[y]);

	for(int i:g[x]) g[y].pb(i);

}

inline void solve(){

	for(int i=1;i<=n;i++) g[i].pb(i),p[i]=i;

	for(int i=n;i;i--){

		bool flag=0;

		for(int j=i-1;j;j--) if(can(i,j)){

			Merge(i,j),flag=1;

			break;

		}

	    sz-=flag,g[i].clear();

	}

}

int main(){

	for(scanf("%d%d",&n,&m),sz=n;m;m--) scanf("%d%d",&U,&V),mmp[U][V]=mmp[V][U]=1;

	solve(),printf("%d\n",sz-1);

	return 0;

}

巴特西

Codeforces 1243 D 0-1 MST

最新文章

热门文章