P1330 封锁阳光大学

题目描述

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

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

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

输入输出格式

输入格式：

第一行：两个整数N，M

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

输出格式：

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

输入输出样例

输入样例#1：

【输入样例1】
3 3
1 2
1 3
2 3

【输入样例2】
3 2
1 2
2 3

输出样例#1：

【输出样例1】
Impossible

【输出样例2】
1

说明

【数据规模】

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

好吧，表示本蒟蒻不懂什么叫黑白染色，所以题解基本看不懂。。

但是我同时用BFS+DFS也AC了

思路：

因为各个点不一定相连

所以我们枚举一边所有的点，对于每个没有访问过的点跑一边DFS，

在DFS的过程中同时访问与该点相连的点，

然后在每次DFS的过程中进行DFS，

算出在该联通分量中，从该点出发，需要放置的数量

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<cstdlib>
  6 #include<queue>
  7 using namespace std;
  8 void read(int & n)
  9 {
 10     char c='+';int x=0;
 11     while(c<'0'||c>'9')
 12     c=getchar();
 13     while(c>='0'&&c<='9')
 14     {
 15         x=x*10+(c-48);
 16         c=getchar();
 17     }
 18     n=x;
 19 }
 20 const int MAXN=10101;
 21 struct node
 22 {
 23     int u,v,nxt;
 24 }edge[MAXN*10+101];
 25 struct dian
 26 {
 27     int bh;
 28     int how;// 0不放，1放 
 29 }sz[MAXN];
 30 int n,m;
 31 int head[MAXN];
 32 int vis1[MAXN];
 33 int vis2[MAXN];
 34 int fang[MAXN];// 记录这个点是否放 
 35 int num=1;
 36 int ans1=0x7fffff,ans2=0,out=0;
 37 void add_edge(int x,int y)
 38 {
 39     edge[num].u=x;
 40     edge[num].v=y;
 41     edge[num].nxt=head[x];
 42     head[x]=num++;
 43 }
 44 void bfs(int p,int fbf)
 45 {
 46     memset(vis2,0,sizeof(vis2));
 47     dian bg;
 48     bg.bh=p;
 49     bg.how=1;
 50     queue<dian>q;
 51     q.push(bg);
 52     while(q.size()!=0)
 53     {
 54         dian now=q.front();
 55         vis2[now.bh]=now.how;
 56         q.pop();
 57         if(now.how==1)
 58         ans2++;
 59         for(int i=head[now.bh];i!=-1;i=edge[i].nxt)
 60         {
 61             dian will;
 62             will.bh=edge[i].v;
 63             if(now.how==1)will.how=2;
 64             else will.how=1;
 65             if(vis2[edge[i].v])
 66             {
 67                 if(vis2[edge[i].v]==now.how)
 68                 {
 69                     printf("Impossible");
 70                     exit(0);
 71                 }
 72                 else continue;
 73             }
 74            
 75             q.push(will);
 76         }
 77     }
 78     ans1=min(ans1,ans2);
 79 }
 80 void dfs(int p)
 81 {
 82     ans2=0;
 83     vis1[p]=1;
 84     bfs(p,1);
 85     for(int i=head[p];i!=-1;i=edge[i].nxt)
 86     {
 87         if(vis1[edge[i].v]==0)
 88         {
 89             ans2=0;
 90             dfs(edge[i].v);    
 91         }
 92     }
 93 }
 94 int main()
 95 {
 96     read(n);read(m);
 97     for(int i=1;i<=n;i++)
 98     head[i]=-1;
 99     for(int i=1;i<=m;i++)
100     {
101         int x,y;
102         read(x);read(y);
103         add_edge(x,y);
104         add_edge(y,x);
105     }
106     int ans=0;
107     for(int i=1;i<=n;i++)
108     {
109         if(vis1[i]==0&&head[i]!=-1)
110         {
111             ans1=0x7ffff;
112             dfs(i);
113             out+=ans1;
114         }
115         
116     }
117     printf("%d",out);
118     return 0;
119 }