@[ko_no_lzx_da](/user/418419) 话说输出Impossible不是40pts吗
by __Shine__ @ 2022-08-08 10:42:35
有个问题，这不一定是个连通图，可能是好几个图，所以你得遍历多次，就像这样：
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e4+10;
const int M=1e5+10;
int n,m;
int col[N];
int sum[3];
struct Edge{
int ver;
int nxt;
}edge[M<<1];
int head[N],tot=-1;
void init(){
memset(head,-1,sizeof(head));
tot=-1;
}
void add(int x,int y){
edge[++tot].ver=y;
edge[tot].nxt=head[x];
head[x]=tot;
}
bool dfs(int u,int fa,int c){
if(col[u]==-c)
return false;
else if(col[u]==c)
return true;
col[u]=c;
sum[c+1]++;
bool ans=1;
for(int i=head[u];~i;i=edge[i].nxt){
int v=edge[i].ver;
if(v==fa)
continue;
ans=(ans&&dfs(v,u,-c));
}
return ans;
}
signed main(){
init();
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){
int u,v;
scanf("%d %d",&u,&v);
add(u,v);
add(v,u);
}
int ans=0;
for(int i=1;i<=n;i++){
if(col[i]==0){
if(!dfs(i,0,1)){
printf("Impossible");
return 0;
}
ans+=min(sum[0],sum[2]);
sum[0]=0;
sum[2]=0;
}
}
printf("%d",ans);
return 0;
}
```
by Makerlove @ 2023-11-14 23:38:27