查看原题请戳这里
因为每条边都只能走一次，所以这道题可以用欧拉路的性质来求解。
我们首先用并查集去记录每一个联通块，然后再统计每一个子图的奇点数，如果是偶数则满足欧拉回路的性质直接ans++ 就好了，如果是奇数，那么需要的蚂蚁数则是奇点数/2
附一下代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| #include<iostream>
#include<cstring>
#include<algorithm>
#define re register
using namespace std;
int read()
{
register int a = 0,f = 1; register char ch;
ch = getchar();
while(ch > '9' || ch < '0') {if(ch == '-') f = -1; ch = getchar();}
while(ch <='9' && ch >='0') {a = a * 10 + ch - 48; ch = getchar();}
return a * f;
}
int n,m,x,y,s,ans,cnt,t,d[100005],fa[100005],use[100005],a[100005],add[100005];
int find(int p)
{
if(fa[p] == p) return p;
return fa[p] = find(fa[p]);
}
void work()
{
m = read();
ans = 0;
for(re int i = 1; i <= n; i++) fa[i] = i;
for(re int i = 1; i <= n; i++) d[i] = 0;
for(re int i = 1; i <= n; i++) a[i] = 0;
for(re int i = 1; i <= n; i++) add[i] = 0;
for(re int i = 1; i <= m; i++)
{
x = read(); y = read();
d[x] ++; d[y] ++;
if(find(x) != find(y))
fa[find(y)] = find(x);
}
for(int i = 1; i<= n; i++)
{
a[find(i)]++;
if(d[i] % 2 == 1) add[find(i)] ++;
}
for(int i = 1; i <= n; i++)
{
if(a[i] <= 1) continue;
else if(add[i] == 0) ans += 1;
else if(add[i] > 0) ans += add[i]/2;
}
cout << ans << endl;
}
int main()
{
while(cin >> n) work();
return 0;
}
|
