Reason for living(noip2017模拟赛)

Posted by yjjr's blog on February 6, 2018

标签:最小生成树,并查集

 

B准备设计施工方案。

设计图是一个n个点m条边的图,小B每次施工可以取图中一个还没有完工的生成森林把它完工。

为了加快施工效率,每次取的时候小B都会最大化当前这个生成森林的边数。请你帮他找出一个符合要求的施工方案。

如果有多个方案,输出任意一种即可。

输入格式

第一行两个整数nm

后面m行,每行两个数ai,bi表示一条边,保证没有自环。

输出格式

m行,每行一个整数,表示这条边属于第几次。如果有多个方案,输出任意一种即可。

样例一

input

5 7
1 2
2 3
3 4
4 5
1 2
2 3
1 2

output

1
1
1
1
3
2
2

限制与约定


分析


每条边加入图中,维护若干个森林,每条边都加入到第一个两个端点不连通的森林中

每一个生成森林都用并查集来维护,二分出第一个两端点不连通的并查集

时间复杂度为O(m log m*a(n))

Code

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define reg(i,a) for(int i=u[a];i;i=e[i].pre)
#define v e[i].to
#define LL long long 
using namespace std;
const int maxn=1e6+10;
inline int read()
{
	int f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
struct edge{int to,pre;}e[maxn<<1];
int u[maxn],l=1;
inline void ins(int a,int b){e[++l]=(edge){b,u[a]},u[a]=l;}
int id[maxn],n,m;
int pre[maxn*2],nxt[maxn*2],mx=0,r[maxn];
bool vis[maxn];
int del(int x){
	nxt[pre[x]]=nxt[x];
	pre[nxt[x]]=pre[x];
}
void insert(int x,int r){
	pre[x]=maxn+r,nxt[x]=nxt[maxn+r];
	pre[nxt[x]]=nxt[pre[x]]=x;
}
void add(int x) {
	del(x);
	r[x]++; mx = max(mx, r[x]);
	insert(x, r[x]);
}
void Forest(){
	rep(i,1,n)insert(i,0);
	rep(i,1,n){
		while(!nxt[maxn+mx])mx--;
		int x=nxt[maxn+mx];del(x);vis[x]=true;
		reg(i,x) if(!vis[v]) id[i>>1]=r[v]+1,add(v);
	}
}

int main()
{
	n=read(),m=read();
	rep(i,1,m){
		int a=read(),b=read();
		ins(a,b),ins(b,a);
	}
	Forest();
	rep(i,1,m) printf("%d\n",id[i]);
	return 0;
}



本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr