自动搬运

查看原文

来自洛谷，原作者为

	孑思 **

搬运于2025-08-24 21:49:08，当前版本为作者最后更新于2018-10-05 10:53:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这是一个求原图的补图联通块个数的题

我们可以知道如果一个点在原图中不能到达另一个点

那么这个点一定可以在补图中到达那个点

但是原图可以到达的点补图不一定不能到达

#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
bool vis[100010],cov[100010];
int cnt,head[100010],nxt[4000100],var[4000100];
int nex[100010],last[100010];
int st[100010],ans;
int n,m;
queue<int> q;
void add(int x,int y) {
	cnt++;
	var[cnt]=y;
	nxt[cnt]=head[x];
	head[x]=cnt;
}//链式向前星，蒟蒻不会vector QWQ
void del(int x) {
	nex[last[x]]=nex[x];
	last[nex[x]]=last[x];
}//删除链表中的某个元素
int main() {
	scanf("%d%d",&n,&m);
	int x,y;
	for(int i=1; i<=m; i++) {
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);//建图
	}
	nex[0]=1;
	for(int i=1; i<n; i++) {
		last[i+1]=i;
		nex[i]=i+1;
	}
	//可以理解为链表，访问的时候可以快一点
	for(int i=1; i<=n; i++) {
		if(!vis[i]) { 
		//如果没被访问过
			st[++ans]=1;//新开一个联通块
			vis[i]=true;//标记
			q.push(i);//入队
			del(i);//删除这个点
			while(!q.empty()) {
				int x=q.front();
				q.pop();
				for(int j=head[x]; j; j=nxt[j]) {
					if(!vis[var[j]]) { 
					//如果原图可以到达的点没有访问过
						cov[var[j]]=true;
						//标记，原图可以访问
					}
				}
				for(int j=nex[0]; j; j=nex[j]) {
					if(!cov[j]) { 
					//访问不到的全都入队，因为在补图里可以访问到
						vis[j]=true;
						//这个点在补图里访问过了
						st[ans]++;
						//联通块里的点的个数++；
						del(j);
						//删除这个点
						q.push(j);
						//入队
					} else cov[j]=false; 
					//如果在原图中可以访问到，那就没他什么事了，恢复原样吧
				}
			}
		}
	}
	sort(st+1,st+ans+1);//排序一下
	printf("%d\n",ans);
	for(int i=1; i<=ans; i++) {
		printf("%d ",st[i]);
	}
	return 0;
	//return 0不知道有没有必要，这几天Claris上课标程永远没有return 0，但是蒟蒻又不敢不打，瑟瑟发抖
}

感谢 奔波儿霸 指出错误