这题恶心死我了。
bfs染色，统计每个联通块两色的个数，ans加它们的最小值。
#include<cstdio> #include<cctype> #include<algorithm> #include<cstring> using namespace std; inline long long max(long long a,long long b){ return a>b?a:b; } inline long long read(){ long long num=0,f=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)){ num=num*10+ch-'0'; ch=getchar(); } return num*f; } struct Edge{ int next,to; }edge[1000010]; int head[1000010],num; int col[10010]; bool flag; inline void add(int from,int to){ edge[++num]=(Edge){head[from],to}; head[from]=num; } int f[1000010],h,t; int c[1000010]; int ans1,ans2,ans; void dfs(){ while(h++<t){ int Col=c[h]; int x=f[h]; if(col[x]&&col[x]!=Col){ flag=1; return; } col[x]=Col; if(col[x]==2) ans1++; if(col[x]==1) ans2++; int Now; if(Col==1) Now=2; if(Col==2) Now=1; for(int i=head[x];i;i=edge[i].next){ if(!col[edge[i].to]){ f[++t]=edge[i].to; c[t]=Now; } } } } int main(){ int n=read(),m=read(); for(int i=1;i<=m;++i){ int from=read(),to=read(); add(from,to); add(to,from); } for(int i=1;i<=n;++i) if(!col[i]){ f[++t]=i; c[t]=1; dfs(); h=0;t=0; ans+=min(ans1,ans2); ans1=0;ans2=0; } if(flag==1){ printf("Impossible"); return 0; } printf("%d",ans); return 0; }