曹是一只爱刷街的老曹,暑假期间,他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹,感到不爽。河蟹决定封锁阳光大学,不让曹刷街。
阳光大学的校园是一张由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 }