【Einstein学画画】

CSP马上到了,赶紧复习图论，顺便写下题解

题目要使画的次数最小，那么我们就可以知道最小的次数为1

于是这道题就是一笔画（欧拉路）板题，甚至还不需要求路径。

先来说一下什么是欧拉路吧：

七桥问题

欧拉说：是否可从某个地方出发，经过每座桥一次,回到原来出发的地方？

然后七桥问题就能转化成如下的一个无向图：

顶点的度，就是指和该顶点相关联的边数。

出度：有向图中从某顶点出发的边数。

入度：有向图中在某顶点结束的边数。

欧拉回路：

若恰通过图中每条边一次回到起点,则称该回路为欧拉(Euler)回路。
具有欧拉回路的图称为欧拉图。
定理1：
一个无向图是欧拉图，当且仅当该图所有顶点度数都是偶数。
一个有向图是欧拉图，当且仅当该图所有顶点度数都是0(入度与出度之和)。
定理2：
存在欧拉回路的条件：图是连通的，且不存在奇点（顶点度数为奇数）

欧拉路（此题解法！）

若从起点到终点的路径恰通过图中每条边一次（起点与终点是不同的点），
则该路径称为欧拉路。
定理1：
存在欧拉路的条件：图是连通的，且存在2个奇点。
如果存在2个奇点，则欧拉路一定是从一个奇点出发，以另一个奇点结束。

注意：一个连通图只可能有偶数个奇点

那么我们可以从欧拉路的介绍，发现只有2个奇点才能1笔画完。

$code:$

#include<bits/stdc++.h>
using namespace std;
int n,m,cnt[1005],ans;
cnt[x]:x的度数
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d %d",&x,&y);
        cnt[x]++;x点度数+1
        cnt[y]++;y点度数+1
    }
    for(int i=1;i<=n;i++)
        if(cnt[i]%2)判断是否为奇点
            ans++;奇点个数+1
    if(ans==2)若只有2个奇点
        puts("1");则可以一笔画完
    return 0;
}

现在我们已经知道如何判断欧拉路了

然后我们可以发现若每多出两个奇点，那么画的次数就会+1

又因为连通图只可能有偶数个奇点

所以，答案为 $ans/2$

$code:$

#include<bits/stdc++.h>
using namespace std;
int n,m,cnt[1005],ans;
cnt[x]:x的度数
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d %d",&x,&y);
        cnt[x]++;x点度数+1
        cnt[y]++;y点度数+1
    }
    for(int i=1;i<=n;i++)
        if(cnt[i]%2)判断是否为奇点
            ans++;奇点个数+1
    printf("%d\n",ans/2);
    return 0;
}

于是我们愉快的交了上去，WA90。。。。。

这是为什么呢？？

根据我们上面的做法，发现下列手购数据过不了：

利用构图我们可以得到这幅图：

咦，发现这3个点都不是奇数点，但也可以一笔画完，所以我们只需要特判一下即可AC

$code:$

#include<bits/stdc++.h>上面代码已经有注释了，就不打了qwq
using namespace std;
int n,m,cnt[1005],ans;
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d %d",&x,&y);
        cnt[x]++;
        cnt[y]++;
    }
    for(int i=1;i<=n;i++){
        if(cnt[i]&1==1)
            ans++;
    }
    if(ans==0)
        puts("1");
    else
        printf("%d\n",ans/2);
    return 0;
}