学习随笔——洛谷题目P1636解答

摘要：欧拉图的应用。

题目原地址如下：https://www.luogu.com.cn/problem/P1636

题目截图如下：

 一笔画问题，考察欧拉回路的定义，即所有节点的入度出度的和都为偶数即可满足欧拉回路的性质。我们为方便分析可加入一条线，发现加入一条边后会改变两个点的度数和，只需寻找奇数点的个数再除2即可。然后需要注意的是我们需要特判“一笔画”情况。

代码如下：

 1 #include <iostream>
 2 using namespace std;
 3 int rem[10000];
 4 int n,m;
 5 int main(){
 6     cin>>n>>m;
 7     for (int i=1;i<=m;i++){
 8         int u,v;
 9         cin>>u>>v;
10         rem[u]++;
11         rem[v]++;
12     }
13     int ans=0;
14     for (int i=1;i<=n;i++){
15         if (rem[i]%2==1)
16             ans++;
17     }
18     if (ans==0)//特判
19         cout<<1;
20     else
21         cout<<ans/2;
22     return 0;
23 }