P1330封锁阳光大学（染色法）-创新互联

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

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

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

第一行两个正整数，表示节点数和边数。 接下来 mm 行，每行两个整数 u,vu,v，表示点 uu 到点 vv 之间有道路相连。

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

输入 #1复制

3 3
1 2
1 3
2 3

输出 #1复制

Impossible

输入 #2复制

3 2
1 2
2 3

输出 #2复制

1

【数据规模】
对于 100\%100% 的数据，1\le n \le 10^41≤n≤104，1\le m \le 10^51≤m≤105，保证没有重边。

呜呜呜，这道题我真真真真真真真没啥思路，于是打开了题解看了看大佬们的想法，学到了一个新的方法，染色法，大佬的思路是这样的：

• 如果一条边两个点一红一蓝，那就是恰好被切断
• 如此看来，所谓占领和不占领其实是等价的。
• 只需要分别尝试两种情况（令这个点是红色或者令这个点是蓝色），看看哪种情况中红点数目最少即可。
• 为什么会Impossible？那是因为，在从第一个点的颜色一直推到所有点的颜色的过程中，有的点会被要求涂上相反的颜色。即当你想把一个点涂成蓝色的时候，却发现它已经是红色了。这就出现无解情况。
• 连通是个永恒的话题。千万不要忘记对不连通的考虑

看了大佬的代码，我真的佩服的五体投地，于是我照葫芦画瓢+自我理解完成了这道题

代码：

#include
using namespace std;
vectorG[10005];
int f=1;
int flag[10005];//-1为没染色，0为蓝色，1为红色
int ans=0;
int dfs(int s,int d)
{
 if(f==0)
 {
     return 0;
 }
 else
 {
     int sum=d;
     flag[s]=d;
     for(int j=0;j      {
         int y=G[s][j];
         if(flag[y]==-1)
         {
             flag[y]=(!d);//这个写法真的很酷的好吧，爱死了
             sum=sum+dfs(y,!d);
         }
         else if(flag[y]==d)
         {
             f=0;
         }
     }
     return sum;
 }
}
int main()
{
 int n,m;
 cin>>n>>m;
 memset(flag,-1,sizeof(flag));

  //图的存储
 for(int i=1;i<=m;i=i+1)
 {
     int u,v;
     cin>>u>>v;
     G[u].push_back(v);
     G[v].push_back(u);
 }

  //有可能图不连通（好恶心）
 for(int i=1;i<=n;i=i+1)
 {
     if(flag[i]==-1)
     {

  //分别涂上红色和蓝色；
         int a=dfs(i,0);
         memset(flag,-1,sizeof(flag));//实现两次遍历并行不悖
         int b=dfs(i,1);
         ans=ans+min(a,b);
     }
     if(f==0)
     {
         break;
     }
 }
 if(f==0)
 {
     cout<<"Impossbile"<  }
 else
 {
     cout<     }
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧