原题链接

题解

1.对于任意一点，只有被河蟹选中和没选中两种状态，变成了染色问题
对于任意一个染了白色的点，其周围的点必须是黑色
对于任意一个染了黑色的点，其周围的点必须是白色
所以初始点染黑色还是染白色答案都是一样的
2.任意两点之间不是绝对联通的，可能有多个图

code

#include<bits/stdc++.h>
using namespace std;
int cnt=0,sum=0;
int color[100005]={0};
vector<int> G[100005];int n,m;
int ss(int now,int wh)//该函数的含义是给now染成wh色时能否完成符合题意的染色
{
    color[now]=wh;
    cnt+=(wh==1);
    sum++;
    int w=1;
    for(int i=0;i<G[now].size();i++)
    {
        int next=G[now][i];
        if(!color[next])w&=ss(next,-1*wh);
        else if(color[next]==color[now])w=0;
    }
    return w;
}
int main()
{

    cin>>n>>m;

    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(!color[i])
        {
            if(ss(i,1))ans+=min(cnt,sum-cnt);
            else
            {
                puts("Impossible");
                return 0;
            }
            sum=0;
            cnt=0;
        }
    }
    cout<<ans<<endl;
    return 0;
}