分类 欧拉回路 下的文章

hiho week49 欧拉回路

在不要求输出路径的情况下只是简单的一笔画问题。小学奥数啊。
虽说咱市奥校没好好听但这还是会的。

判定条件:存在欧拉回路当且仅当奇数度的点数为2或0。

不过咱不会严格证明啊。。。要死。。。
再次膜拜欧拉神!

#include <iostream>
using namespace std;
const int maxn = 1e4 + 10;
int island[maxn] = {0};
int main()
{
    int n, m;
    cin>>n>>m;
    while(m--)
    {
        int u, v;
        cin>>u>>v;
        island[u]++;
        island[v]++;
    }
    int cnt = 0;
    for(int i = 1; i <= n; i++)
        if(island[i] & 1)
            cnt++;
    if(cnt == 2 || cnt == 0)
        cout<<"Full"<<endl;
    else
        cout<<"Part"<<endl;
    return 0;
}