213
by welking @ 2017-09-25 13:04:24
@[张子杰](/space/show?uid=45163) ???
by gwj12345 @ 2017-09-25 13:37:15
```cpp
/*
已AC
*/
#include<iostream>
#include<algorithm>
#include<vector>
#define maxn 11000
using namespace std;
int col[maxn], flag, num[5], ans;//mdzz数组开少了改了一下午
vector<int>G[maxn];
void color(int u, int c){
col[u] = c;
num[c+1]++;
for(int i = 0; i < G[u].size(); i++){
int v = G[u][i];
if(col[v] == col[u])flag = 1;
if(!col[v])color(v, -c);
}
}
int main(){
int n, m;
cin>>n>>m;
for(int i = 1; i <= m; i++){
int a, b; cin>>a>>b;
G[a].push_back(b);
G[b].push_back(a);
}
for(int i = 1; i <= n; i++)if(!col[i]){
if(flag)break;
num[0] = num[2] = 0;
color(i,1);
ans += min(num[0],num[2]);
}
if(flag)cout<<"Impossible\n";
else cout<<min(ans, n-ans)<<"\n";
return 0;
}
```
by gwj12345 @ 2017-09-25 18:24:24
我和你错的一样,一开始也是最后一起取的min,应该是对于每个联通分量都要取一次min
by xunzhen @ 2017-11-02 21:23:37
@[xunzhen](/space/show?uid=9612) ~~挖坟警告~~
翻讨论的时候突然发现,,,我也是这样错的
by 天才byt @ 2019-04-12 13:14:08
~~挖坟警告~~$\times 2$
~~这么错的~~$+1$
by 泰勒斯威夫特 @ 2019-05-26 15:44:00