题目描述

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

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

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

原题链接

Solution

简单说，就是将给定的图（不一定联通）进行“染色”。因为“当两只河蟹封锁了相邻的两个点时，他们会发生冲突”，所以用两种颜色。

注意：给定的图不一定是联通的

判联通：

方法一：并查集，父节点相同的为一张图（可参考蒟蒻的OI笔记）

方法二：Floyd

AC代码：

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
int n,m,sum1,sum2,ans;  //n为节点数，m为边数，sum1.sum2用于染色点的统计，ans为最后答案
int f[10001],vis[10001],du[10001];   //f用于并查集判联通，vis用于染色（1，2分别是两种颜色），du用于统计节点的度数
bool flag;   //flag用于判是否有解.false表有解.true无解
vector<int> g[10001];  //vector玄学建图
//并查集
int find(int x){
    if(x!=f[x]) f[x]=find(f[x]);
    return f[x];
}
void dfs(int x){
    if(vis[x]==1) sum1++;
    if(vis[x]==2) sum2++;  //记录色数
    if(flag==true) return ; 
    for(int i=0;i<g[x].size();i++){
        if(vis[x]!=vis[g[x][i]]&&vis[g[x][i]]!=0) continue; //已经染好，跳过
        if(vis[x]==vis[g[x][i]]){ //与之前有冲突，无解
            flag=true;
            break;
        }
        vis[g[x][i]]=3-vis[x];
        dfs(g[x][i]);
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        int x=find(u);
        int y=find(v);
        if(x!=y) f[y]=x;  //并查集
        g[u].push_back(v);
        g[v].push_back(u);  //无向图，双向建边
        du[u]++;
        du[v]++;   //记录度数
    }
    for(int i=1;i<=n;i++){
        sum1=0,sum2=0;  //sum1.sum2表每张图的两种色数，搜索前清零
        if(f[i]==i&&du[i]>0){  //搜索每张独立且有边的图
            vis[i]=1;  //起点色别其实无所谓，效果都一样
            dfs(i);
            ans+=min(sum1,sum2);
        }
        if(flag==true){
            cout<<"Impossible";
            return 0;
        }
    }
    cout<<ans;
    return 0;
}