文章

4225

粉丝

133

获赞

608

访问

667w

头像
01最小生成树 题解:补图的连通图数量
P5221 北京大学2024年机试题
发布于2025年2月19日 22:44
阅读数 127

思路:

1.没有给出的边权值都为0,因此就是求补图的连通图数量-1;
2.从1遍历到n,假设遍历到i,我们求出i所在的连通图的其它点,并做上标记,在遍历时,就跳过做完标记的点,遍历了ans次,就说明有ans个连通图;
3.如何求出i所在的连通图的其它点呢?我们用双链表存储未被遍历过的点(节省时间),遍历和i相连权值为1的边,如果边的另一个端点未被遍历过,我们就做一个标记,接着遍历所有未被遍历过的点(存储在双链表中),如果这个点没有被做标记,那么就说明这个点和i有权值为0的边,利用bfs的思想,我们将这个点加入队列,队列为空后,i所在的连通图里的所有点就被bfs出来了;

#include<bits/stdc++.h>
#define fi first
#define sc second
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define pt(a) cerr<<a<<"---\n"
#define rp(i,n) for(int i=0;i<n;i++)
#define rpn(i,n) for(int i=1;i<=n;i++)
using namespace std;
const int maxn=1e5+99; 
int n,m,pre[maxn],nxt[maxn],vst[maxn],flag[maxn];
vector<int> G[maxn];
void del(int i){nxt[pre[i]]=nxt[i];if(~nxt[i])pre[nxt[i]]=pre[i];}
void bfs(int id){
	queue<int> que;
	que.push(id);
	while(!que.empty()){
		int now=que.front(); que.pop();
		for(int x:G[now]) if(!vst[x]) flag[x]=1;
		for(int i=nxt[0];~i;i=nxt[i]){
			if(flag[i]) flag[i]=0;
			else vst[i]=1,que.push(i...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发