题解 P1636 【Einstein学画画】

· · 题解

kcm 布置的题。。蒟蒻前来水篇题解/ts

我们都知道，一张图只要有0/2 个奇点，就能一笔画。

不难想到，该图若不能一笔画，则需要奇点数/2 笔才能画出。

那就可以用邻接表来实现了，读入各无向边，统计奇点个数，然后判断。

看到大佬们都直接用数组存，没存边，用vector 的蒟蒻瑟瑟发抖。

kcm 为啥不教vector呀，vector 大法好啊

Code

#include<cstdio>
#include<vector>
using namespace std;
vector<int> g[1000];
int n,m,x,y,num;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);//建边
    }
    for(int i=1;i<=n;++i)
        if(g[i].size()%2==1)
            ++num;//num为奇点数
    if(num==2||num==0)
        printf("1");//能一笔画
    else
        printf("%d",num/2);//不能一笔画
    return 0;
}

End.