解题思路
显然相邻的两个点是不能够同时存在河蟹的，那就对每两个相邻的点进行染色操作，一个染成黑点，一个染成白点。一个很容易想到的事实就是如果在染色的过程中对某一点的操作和之前染的色冲突，那么河蟹就无法成功阻拦老曹刷街
附上代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int maxn = 2e5+
3;
int n, m, fir[maxn], nx[maxn], u[maxn], v[maxn];
int col[maxn], cnt, sum[
4], Ans;
bool vis[maxn];
struct node {
int n1, n2, x, tot, c;
}tmp;
queue<node>
Q;
inline void addedge(
int fr,
int to) {
nx[++cnt] =
fir[fr];
u[cnt] = fr, v[cnt] =
to;
fir[fr] =
cnt;
}
inline bool dfs(
int s,
int color) {
if(vis[s]) {
if(color == col[s])
return true;
else return false;
}
vis[s] =
true;
col[s] =
color;
sum[col[s]] ++
;
int k =
fir[s];
bool fin =
true;
while(k != -
1) {
fin = fin && dfs(v[k], col[s] ?
0 :
1);
k =
nx[k];
}
return fin;
}
int main() {
scanf("%d%d", &n, &
m);
memset(fir, -
1,
sizeof(fir));
int x, y;
for(
int i=
1; i<=m; i++
) {
scanf("%d%d", &x, &
y);
addedge(x, y), addedge(y, x);
}
for(
int i=
1; i<=n; i++
) {
if(vis[i])
continue;
sum[0] = sum[
1] =
0;
if(!dfs(i,
0)) {
printf("Impossible\n");
return 0;
}
Ans += min(sum[
1], sum[
0]);
}
printf("%d", Ans);
}
转载于:https://www.cnblogs.com/bljfy/p/9463782.html
相关资源：锣鼓声声迎新春——新年工作计划ppt模板.zip
