Time Limit: 1 second

Memory Limit: 128 MB

【问题描述】

曹是一只爱刷街的老曹，暑假期间，他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹，感到不爽。河蟹决定封锁阳光大学，不让曹刷街。 阳光大学的校园是一张由N个点构成的无向图，N个点之间由M条道路连接。每只河蟹可以对一个点进行封锁，当某个点被封锁后，与这个点相连的道路就被封锁了，曹就无法在与这些道路上刷街了。非常悲剧的一点是，河蟹是一种不和谐的生物，当两只河蟹封锁了相邻的两个点时，他们会发生冲突。 询问：最少需要多少只河蟹，可以封锁所有道路并且不发生冲突。

【输入格式】

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

【输出格式】

如果不能够对大学进封锁，则输出Impossible，否则输出所需要的最小河蟹数目。

【数据规模】

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

Sample Input1

3 3

1 2

1 3

2 3

Sample Output1

Impossible

Sample Input2

3 2

1 2

2 3

Sample Output2

1

【题解】

简单的方法是对所有点进行染色。



如上图。在相同的颜色处放河蟹。即可占据所有的道路。且不会发生冲突。即相邻点染成不同的颜色。

然后要求最小。就要看在0处放河蟹放得比较少还是在1处会放得比较少。取其中的较小值即可。

然后可能会有多个子图的情况。注意一下即可。

染色可以用广搜进行。顺便可以判断会不会出现impossible的情况。

【代码】

#include <cstdio>

#include <cstring>

#include <stdlib.h>

struct node//很久没打链表了。练一下。

{

    int en;

    node *next;

};

int n, m,color[10001],dl[10001],final_ans = 0;//color[]是给每个点染的颜色。

node *head[10001],*tail[10001];//表示邻接表的头结点和尾节点。

bool bo[10001] = { 0 };//判断某个点是否染色过。

void input_data();

void add(int,int);

void get_ans();

int bfs(int);

void output_ans();

int main()

{

    //freopen("F:\\rush.txt", "r", stdin);

    //freopen("F:\\rush_out.txt", "w", stdout);

    input_data();

    get_ans();

    output_ans();

    return 0;

}

void output_ans()//输出最后的答案。

{

    printf("%d", final_ans);

}

int bfs(int key)//从key点开始广搜进行染色。

{

    bo[key] = true;

    color[key] = 0;

    int h = 0, t = 1;

    dl[1] = key;//加入队列

    while (h != t)

    {

        h++;//取出头结点

        int x = dl[h];

        node *temp = head[x]->next;//寻找其出度。是双向边。

        while (temp != NULL)

        {

            int y = temp->en;

            if (!bo[y])//如果之前没有染色过

            {

                color[y] = 1 - color[x];//给其染上和x不同的颜色

                bo[y] = true;//标记它已经染色过

                t++;//然后把它加入到队列中，一是为了继续染色。而是为了判断它和它的邻点是否冲突。

                dl[t] = y;

            }

            else

                if (color[y] == color[x])//如果出度已经染过色且颜色发生冲突。则输出不可能

                {

                    printf("Impossible");

                    exit(0);//直接结束所有的程序。

                }

            temp = temp->next;//寻找下一个出度。

        }

    }

    int ans[2];//算出把河蟹放在颜色0和颜色1分别所需要的数目

    ans[0] = 0; ans[1] = 0;

    for (int i = 1; i <= t; i++)

        ans[color[dl[i]]]++;

    if (ans[0] > ans[1])//返回其中的较小值 bfs是一个返回Int的函数。

        return ans[1];

    else

        return ans[0];

}

void get_ans()

{

    for (int i = 1; i <= n; i++)

        if (!bo[i])//因为可能出现多个子图，所以可能要多次染色。

            final_ans+=bfs(i);

}

void add(int x, int y)//加入一条边，从x->y，然后执行add(x,y),add(y,x)就变成无向边了。

{

    tail[x]->next = new node;

    tail[x] = tail[x]->next;

    tail[x]->next = NULL;

    tail[x]->en = y;

}

void input_data()

{

    scanf("%d%d", &n, &m);//输入n和m

    for (int i = 1; i <= n; i++)//初始化邻接表

    {

        head[i] = new node;

        head[i]->next = NULL;

        tail[i] = head[i];

    }

    for (int i = 1; i <= m; i++)//输入图的信息。

    {

        int x, y;

        scanf("%d%d", &x, &y);

        add(x, y);

        add(y, x);

    }

}