忘说了
代码30pts.....
by hhwwff @ 2023-08-18 22:01:28
二分图跑完其中一种颜色的点的个数不一定就是 $n/2$ 呀 =)
by d95a_4c1d @ 2023-08-18 22:37:25
@[d95a_4c1d](/user/764367) 大佬,我明白
那个代码放在那里只是听让各位人士看的更明白一些罢了。。
by hhwwff @ 2023-08-19 10:03:27
改了亿下50pts了...
```
#include <bits/stdc++.h>
using namespace std;
int n,m,jhf,e;
vector <int> p[100010];
int v[10010];
int v11[10010];
int u[100010];
void dfs(int x,int b){
if(e == 1){
if(b % 2 == 1){
jhf = 1;
}
}
if(jhf == 1){
return;
}
int hf = 0;
for(int i = 0;i < p[x].size();i++){
if(v11[p[x][i]] == 0){
v11[p[x][i]] = 1;
dfs(v[p[x][i]],b++);
v11[p[x][i]] = 0;
}
if(v11[p[x][i]] == 1){
hf++;
}
if(hf >= 2){
e = 1;
}
}
}
int main()
{
cin >> n >> m;
int v1;
for(int i = 1;i <= m;i++){
cin >> u[i] >> v1;
p[u[i]].push_back(v1);
p[v1].push_back(u[i]);
}
for(int i = 1;i <= m;i++){
if(v[u[i]] == 0){
v[u[i]] = 1;
v11[u[i]] = 1;
dfs(u[i],0);
}
}
if(jhf == 1){
cout << "Impossible" << endl;
return 0;
}
if(m % 2 == 1){
cout << ceil(m / 2) << endl;
}else{
cout << m / 2 << endl;
}
return 0;
}
```
#2-5,#7wa
by hhwwff @ 2023-08-19 10:26:54
```cpp
if(v11[p[x][i]] == 0){
v11[p[x][i]] = 1;
dfs(v[p[x][i]],b++);
v11[p[x][i]] = 0;
}
```
把第3行改为:
```cpp
dfs(p[x][i],b++);
```
后少了十分..
第一个点也错了...........
by hhwwff @ 2023-08-19 10:39:00
@[hewenfeng_00544](/user/556815) 万一图不连通呢qwq
by d95a_4c1d @ 2023-08-20 15:08:39
我是染色做的,图可能是不连通的,每个连通块中找染色较少的颜色数量,最后把各个连通块的数加起来
by in_3 @ 2023-09-08 15:41:07
@[hewenfeng_00544](/user/556815) 我已经切掉了,dalao解决了吗qwq要是解决了我就先跑了
by d95a_4c1d @ 2023-09-15 21:51:21