社区讨论
最后一个点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 条回复,欢迎继续交流。
正在加载回复...