题解 P1636 【Einstein学画画】

ww3113306 · 2017-07-19 12:05:33 · 题解

因为画一次最多画完2个边为奇数的点，所以只要统计边为奇数的点为多少就行了，这里我用了链表来存图，可能略复杂

#include<bits/stdc++.h>
using namespace std;
struct abc{
    int t,next;    
};
struct ab{
    int num,j;//j表示这个点有多少条边
};
int n,m,tot=0,j;abc h[205000];ab head[1500];
void add(int x,int x2)//加边
{
    tot++;
    h[tot].t=x2;
    h[tot].next=head[x].num;
    head[x].num=tot;
    head[x].j++;
}
int main()
{
    int i,k,number=0,times=0,k2;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d",&k);
        scanf("%d",&k2);
        add(k,k2);//因为无向图，所以要加两次边
        add(k2,k);
    }
    for(i=1;i<=n;i++)//从1到n搜索边为奇数的点
        if(head[i].j%2==1)
            number++;//搜索到一个，number++
    times+=number/2;//笔画数先加number/2
    if(number%2==1) times++;//如果number是个奇数，那么这个点就需要额外画一笔，才能画到
    if(times==0) {printf("1");return 0;}//这个是第二个点的特判，第二个点全部都是边为偶数的点，但显然要画完还是要画一笔的
    printf("%d",times);//输出笔画数
    return 0;    
}