bfs->洛谷P1330 *阳光大学
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
vector <int> g[1000010];
int vis[1000010];
int a[10];
int col[1000010];
queue <int> que;
void bfs(int x)
{
while(!que.empty()){
int tmp = que.front();
vis[tmp] = 1;
que.pop();
for(int i=0;i<g[tmp].size();i++){
int tmnp = g[tmp][i];
if(!vis[tmnp]){
que.push(tmnp);
vis[tmnp] = 1;
col[tmnp] = (col[tmp]+1)%2;
a[col[tmnp]]++;
}
else if(col[tmp]==col[tmnp]){
a[0] = -1;
a[1] = -1;
return ;
}
}
}
}
int main()
{
int n,m;
cin>>n>>m;
int aa,bb;
while(m--){
cin>>aa>>bb;
g[aa].push_back(bb);
g[bb].push_back(aa);
}
memset(col,-1,sizeof(col));
int ans = 0;
int flag = 0;
for(int i=1;i<=n;i++){
if(!vis[i]){
a[0] = 1;
a[1] = 0;
col[i] = 0;
que.push(i);
bfs(i);
if(a[0]==-1||a[1]==-1){
flag = 1;
}
else{
ans += min(a[0],a[1]);
}
}
}
if(flag)
cout<<"Impossible";
else
cout<<ans;
return 0;
}