【hihocoder】欧拉路径 并查集判连通

#include<iostream>

#include<cstdio>

#include<string>

#include<cstring>

#include<algorithm>

#include<vector>

#include<queue>

using namespace std;

int n,m;

const int maxn=1e4+;

const int maxm=5e4+;

int degree[maxn];

int fa[maxn];

struct edge{

    int to;

    int nxt;

}e[*maxm];

int head[maxn];

int tot;

void init(){

    memset(head,-,sizeof(head));

    tot=;

    memset(degree,,sizeof(degree));

}

void add(int u,int v){

    e[tot].to=v;

    e[tot].nxt=head[u];

    head[u]=tot++;

}

int getfa(int u){

    if(fa[u]==u) return u;

    return fa[u]=getfa(fa[u]);

}

void merge(int u,int v){

    int fu=getfa(u);

    int fv=getfa(v);

    if(fu!=fv){

        fa[u]=fa[v];

    }

}

bool judge(){

    for(int i=;i<=n;i++){

        fa[i]=i;

    }

    for(int u=;u<=n;u++){

        for(int i=head[u];i!=-;i=e[i].nxt){

            int v=e[i].to;

            merge(u,v);

        }

    }

    int cnt=;

    for(int i=;i<=n;i++){

        if(fa[i]==i) cnt++;

    }

    if(cnt==) return true;

    return false;

}

int main(){

    while(~scanf("%d%d",&n,&m)){

        init();

        int u,v;

        for(int i=;i<=m;i++){

            scanf("%d%d",&u,&v);

            degree[u]++;

            degree[v]++;

            add(u,v);

            add(v,u);

        }

        bool connected=judge();

        if(!connected){

            printf("Part\n");

            continue;

        }

        int cnt=;

        for(int i=;i<=n;i++){

            if(degree[i]%) cnt++;

        }

        if(cnt==||cnt==) printf("Full\n");

        else printf("Part\n");

    }

    return ;

}