社区讨论

最后一个点MLE希望大家帮忙找一下错!

P1330封锁阳光大学参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@mi6yvgcy
此快照首次捕获于
2025/11/20 13:04
4 个月前
此快照最后确认于
2025/11/20 13:04
4 个月前
查看原帖
CPP
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<queue>
using namespace std;
const int maxn=5*1e4+5;
int n,m,head[maxn*2],k,col[maxn],ans,c1,c2,mx;
struct node{
	int nxt,v;
}e[maxn*2];
void add(int u,int vi){
	e[++k].v=vi;
	e[k].nxt=head[u];
	head[u]=k;
}
queue<int>q;
void  dfs(int x,int fa){
	for(int i=head[x];i;i=e[i].nxt){
		int vi=e[i].v;
		if(vi==fa) continue;
		if(!col[vi]){
			if(col[x]==1){
				c2++;
				col[vi]=2;
				dfs(vi,x);
			}
			else{
				c1++;
				col[vi]=1;
				dfs(vi,x);
			}
		}
		else{
			if(col[vi]==col[x]){
				printf("Impossible");
				exit(0);
			}
			else{
				dfs(vi,x);
			}
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		add(a,b);
		add(b,a);
	}
	for(int i=1;i<=n;i++){
		if(!col[i]){
			c1=0,c2=0;
			col[i]=1;
			c1++;
			dfs(i,i);
			ans+=min(c1,c2);
		}
	}
	printf("%d",ans);
	return 0;
}

回复

1 条回复,欢迎继续交流。

正在加载回复...