本文共 836 字，大约阅读时间需要 2 分钟。

题目描述

曹是一只爱刷街的老曹，暑假期间，他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹，感到不爽。河蟹决定封锁阳光大学，不让曹刷街。

阳光大学的校园是一张由N个点构成的无向图，N个点之间由M条道路连接。每只河蟹可以对一个点进行封锁，当某个点被封锁后，与这个点相连的道路就被封锁了，曹就无法在与这些道路上刷街了。非常悲剧的一点是，河蟹是一种不和谐的生物，当两只河蟹封锁了相邻的两个点时，他们会发生冲突。

询问：最少需要多少只河蟹，可以封锁所有道路并且不发生冲突。

输入输出格式

第一行：两个整数N，M

接下来M行：每行两个整数A，B，表示点A到点B之间有道路相连。

输出格式：

仅一行：如果河蟹无法封锁所有道路，则输出“Impossible”，否则输出一个整数，表示最少需要多少只河蟹。

输入输出样例

输入样例#1：

【输入样例2】

输出样例#1：

【输出样例2】

说明

【数据规模】

1<=N<=10000，1<=M<=100000，任意两点之间最多有一条道路。

二分图染色模板题。。。

#include
   
    #include
    
     #include
     
      using namespace std;vector
      
       v[10001];int n,m,cnt1,cnt2,tot,col[10001];bool flg,vis[10001];void dfs(int u,int fcol){    vis[u]=1;    col[u]=fcol^1;    if(!col[u])        cnt1++;    else        cnt2++;    for(int i=0;i
      
     
    
   

转载地址：https://blog.csdn.net/Rlt1296/article/details/51893429 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！