题解 P1636 【Einstein学画画】

LGG_ · 2019-09-28 15:50:58 · 题解

先看了解一笔画的性质

转载

一笔画的判定条件：奇点数为0或2，奇点数就是从该点引出的线的数目为奇数（以下要注意，突出来的线）

奇点数为2的倍数：从该点引出的线为奇数的线的点数目有Ｎ个,则说明该图形为Ｎ/2笔画成。如下图，红色圈圈都为奇点数为8，4笔画。

.....

链接

然后就是这个极其简单的代码

#include<iostream>
using namespace std;
int dx[1001],g[1001][1001];
int n,m,c;
int a,b;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>a>>b;
        g[a][b]=g[b][a]=1;
        dx[a]++;
        dx[b]++;//入度和出度
    }
    for(int i=1;i<=n;i++)
    if(dx[i]%2==1)c++;
    if(c!=0)cout<<c/2;
    else cout<<"1";
    return 0;//好习惯
}

（复习qwq