POI 14th Offices

24-04-10   15:57       Offices      OK           100                                                                                             .


這題作法好多XD

學了一種新建圖方式，不用struct的adjacent list








反正就是開一個Linked-list 維護沒走過的點

這樣bfs均攤O(V)

//**************************************

#include<algorithm>
#define V 100100
#define E 4000200
int ej[E], st[V], enx[E], n, m, cnt, nxt[V], pre[V], a, b, p, c[V], q[V], v[V];
int s[3000], pp[V];
int main(){
	scanf("%d%d", &n, &m);
	for(int i=0; i<=n; i++){nxt[i]= i+1; pre[i+1]= i;}
	for(int i=1; i<=m; i++){
		scanf("%d%d", &a, &b);
		ej[i]= b; p= st[a]; st[a]= i; enx[i]= p;
		ej[i+m]= a; p= st[b]; st[b]= i+m; enx[i+m]= p;
	}
	for(int i=1; i<=n; i= nxt[i]){
		a=b=0;
		q[b]= i; b++;
		while(a!=b){
			p= q[a]; a++;
			v[p]= i; pp[i]++;
			for(int j=st[p]; j; j=enx[j])c[ej[j]]= p;
			for(int j=nxt[i]; j<=n; j=nxt[j])
				if(c[j]!= p){
					q[b]= j; b++;
					nxt[pre[j]]= nxt[j];
					pre[nxt[j]]= pre[j];
				}
		}
	}
	for(int i=1; i<=n; i++)
		if(v[i]==i){
			s[cnt]= pp[i];
			cnt++;
		}
	std::sort(s, s+cnt);
	printf("%d\n", cnt);
	for(int i=0; i<cnt; i++, putchar(i==cnt? '\n': ' '))
		printf("%d",s[i]);
}