题意描述：

（唐）曹是一只爱刷街的老（唐）曹……

暑假期间，他每天都欢快地在阳光大学的校园里刷街。

河蟹看到欢快的曹，感到不爽。河蟹决定封锁阳光大学，不让曹（唐）刷街。

阳光大学的校园是一张由N个点构成的无向图，N个点之间由M条道路连接。

每只河蟹可以对一个点进行封锁，当某个点被封锁后，与这个点相连的道路就被封锁了，曹（唐）就无法在与这些道路上刷街了。

但非常悲剧的一点是，河蟹是一种不和谐的生物，当两只河蟹封锁了相邻的两个点时，他们会发生冲突。

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

输入格式：

第一行：两个整数N，M

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

输出格式：

仅输出一行

如果河蟹无法封锁所有道路，则输出一个字符串“Impossible”

否则输出一个整数，表示最少需要多少只河蟹

Input & Output 's examples

Input 's eg 1

3 3
1 2
1 3
2 3

Output 's eg 1

Impossible

Input 's eg 2

3 3
1 2
2 3

Output 's eg 2

1

分析

一道好题，如果有思路的话还是很好写的。

下面，我们就来分析几种做法。

枚举

首先，你可能本着枚举法无敌论的原则选择枚举

但是……

超高的时间复杂度会让你呕吐的

我们可以分析一下，假设这张图是有解的，那么枚举一定会枚举出所有Impossible的情况才能确定有解。

而Impossible的数量与点数有关，如果大一点，就可能有上百万种……（这就是为什么暴力比正解还难写）

因此，枚举是不可以的

直接dfs & bfs

同理，会被卡死在时间复杂度上，不多解释（其实是作者太懒了……）

正解

很显然，这是一个非连通图，所以我们可以把它拆成许多个连通子图来做

多读几遍题目，不难发现两个关键点：

1.每只河蟹可以对一个点进行封锁，当某个点被封锁后，与这个点相连的道路就被封锁了
2.当两只河蟹封锁了相邻的两个点时，他们会发生冲突。

翻译成人话就是

一条边的两个端点上 必须有 且 只有一个端点 上有河蟹

是不是明白了什么？

这就是一道二分图染色题啊！（ps.即把相邻的两个点染成不同的颜色）

对于一张连通子图，只有三种染色情况，分别是color1 ，color2和Impossible

所以，我们把所有子图染一遍色，如果有一个为Impossible就输出答案，如果没有，就把结果加起来取min即可

是不是很简单啊（逃）~

附件（AC标程，防作弊已开启）

#include<iostream>
#include<algorithm>
#define N 100001

using namespace std;

struct Edge{
    int to;
    int last;    //一只可爱的链式前向星 
}edge[N];

int end[N];
int edge_number;

void add_edge(int from , int to){
    edge[++edge_number].to = to;
    edge[edge_number].last = end[from];
    end[from] = edge_number;
}

int ans;        //最后的答案 
int color[N];    //表示该点的颜***ool visit[N];    //表示该点是否染过色
int number[2];    //表示该颜色的点的数量 


bool draw(int s , int color2){    //color2表示该点染成的颜色,返回的如果为false，则为Impossible 
    if(visit[s]){
        if(color[s] == color2){
            return true;
        }//特判，如果该点染过色，就判断染得颜色是否与本次的一致 
        else{
            return false;
        }
    }
    visit[s] = true;
    color[s] = color2;    //给该点染色 
    number[color2] ++;    //该颜色的点数量+1 
    bool p = true;
    for(int i = end[s]; i != 0 && p != 0; i = edge[i].last){
        p = p && draw(edge[i].to , !color2);    //判断与另一端点是否冲突 
    }
    return p;
}

void work(int ans){
    ans+= 1;
}

int n , m;

int main(){
    int a , b;
    cin >> n >> m;
    for(int i = 1; i <= m; i ++){
        cin >> a >> b;
        add_edge(a , b);
        add_edge(b , a);
    } 
    for(int i = 1; i <= n; i ++){
        if(visit[i] == true){
            continue;
        }
        number[0] = 0;//每次清空该颜色的数量 
        number[1] = 0;
        if(!draw(i , 0)){
            cout << "Impossible" <<endl;
            return 0;
        }
        ans = ans + min(number[0] , number[1]);
    } 
    work(ans);
    cout << ans <<endl;

    return 0;
}

THE END