#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
bool v[N],c[N];
vector<int>e[N];
int cnt[2],ans;
void dfs(int x)
{
	cnt[c[x]]++;
	for(int y:e[x])
		if(!v[y])c[y]=c[x]^1,v[y]=1,dfs(y);
		else if(c[x]==c[y])puts("Impossible"),exit(0);
}
int main()
{
	int n,m;scanf("%d%d",&n,&m);
	for(int i=1,u,v;i<=m;i++)
	{
		scanf("%d%d",&u,&v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
	for(int i=1;i<=n;i++)if(!v[i])
	{
		cnt[0]=cnt[1]=0;c[i]=v[i]=1;
		dfs(i);ans+=min(cnt[0],cnt[1]);
	}
	printf("%d\n",ans);return 0;
}

思路

使用二分图，用 DFS 算法对图进行染色。

在 DFS 遍历中，首先判断的就是相邻节点是否同色，若同色则说明无法封锁道路。随后，DFS 会计算最大匹配数，最大匹配数即为最终答案。

AC CODE

#include<bits/stdc++.h>
using namespace std;
vector<int> e[100010];
int n,m,s,t,k,num[10],c[100010],ans,f;
void dfs(int u){
	for(int v:e[u]){
		if(c[v]){
			if(c[v]==c[u]){
				f=1;
			}
			continue;
		}
		c[v]=3-c[u];
		num[c[v]]++;
		dfs(v);
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>s>>t;
		e[s].push_back(t);
		e[t].push_back(s);
	}
	for(int i=1;i<=n;i++){
		if(!c[i]){
			num[1]=1,num[2]=0,c[i]=1;
            dfs(i);
			ans+=min(num[1],num[2]);
		}
	}
	if(f)cout<<"Impossible";
	else cout<<ans;
	return 0;
}