P1330 封锁阳光大学

题目描述

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

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

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

输入格式

第一行两个正整数，表示节点数和边数。接下来 \(m\) 行，每行两个整数 \(u\)、\(v\) ，表示点 \(u\) 到点 \(v\) 之间有道路相连。

输出格式

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

输入输出样例

输入 #1

输出 #1

Impossible

输入 #2

输出 #2

说明/提示

【数据规模】

对于所有的数据，\(1\leq n\leq 10^4\)，\(1\leq m\leq 10^5\)，保证没有重边。

思路

想要把所有的道路封住，将设断点（放河蟹的点），不妨把断开的点设为黑点，不断开的为白点，在数组中就可以设黑点为 \(1\) ，白点为 \(0\) 。

枚举 \(1-n\) 的点，依次染色，染黑白都无所谓，既可以断黑点不断白点，又可以断白点不断黑点，都可以使街道全部封闭（可以自己模拟一个简单的样例），所以到最后取最小值便可。

但如果染色过程中，出现冲突，即刻弹出，输出 \(Impossible\) 。

代码

#include <bits/stdc++.h>

using namespace std;

const int maxn=10000+50;

int n,m;

int tot;

int head[maxn];

int vis[maxn];

int col[maxn];//i点被染成的颜色

int ans1;//被染为黑点的个数

int ans0;//被染为白点的个数

int ans;

struct Edge{

    int next,to;

}e[maxn];

void Add(int u,int v){//前向星加边

    e[++tot].to=v;

    e[tot].next=head[u];

    head[u]=tot;

}

bool dfs(int u,int color){//将u点染为color

    if(vis[u]){//如果被访问过

        if(col[u]==color){//且之前染的颜色与现在要染的颜色相同，合法

            return true;

        }else{//若不同，不合法

            return false;

        }

    }

    vis[u]=1;//设为已被访问

    col[u]=color;//染色

    if(color==1)ans1++;//记录被染为黑点的个数

    else ans0++;//记录被染为白点的个数

    bool en=true;

    for(int i=head[u];i&&en;i=e[i].next){

        int v=e[i].to;

        en=en&&dfs(v,1-color);//若v点不能被染为(1-color)，则不合法

    }

    return en;

}

int main(){

    scanf("%d%d",&n,&m);

    for(int i=1;i<=m;i++){

        int u,v;

        scanf("%d%d",&u,&v);

        Add(u,v);//无向图

        Add(v,u);

    }

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

        if(vis[i])continue;//若已被访问过，跳过

        ans0=0;

        ans1=0;

        if(!dfs(i,0)){//将i点染为白色，但无法合法地染色

            printf("Impossible\n");

            return 0;

        }

        ans+=min(ans0,ans1);//白点、黑点相互转换

    }

    printf("%d\n",ans);

    return 0;

}

巴特西

P1330 封锁阳光大学——深度优先搜索DFS