hihocoder #1176 : 欧拉路·一

╰半橙微兮° 2022-08-02 15:00 147阅读 0赞

欧拉路径：无向图存在欧拉路径的条件是：图是联通的（并查集判断pre\[ \]数组根节点的个数） 、度数（入度加出度）为奇数的点有且仅有2个或者有0个。

有向图存在欧拉路径的条件是：图示联通的、每个点都入度等于出度 或者只有两个点相连（特判就行）。

欧拉回路：无向图存在欧拉回路的条件是：图是联通的，度数为奇数的点为0。

有向图存在欧拉回路的条件是：图是连通的，每个点都是入度等于出度。

#include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    
    int rd[10010];
    int pre[10010];
    int find(int x)
    {
        if(x==pre[x])return x;
        return pre[x]=find(pre[x]);
    }
    int main()
    {
        int n,m;
        while(~scanf("%d%d",&n,&m))
        {
            for(int i=0;i<=n;i++)pre[i]=i;
            bool flag;
            mem(rd,0);
            while(m--)
            {
                int t1=in(),t2=in();
                rd[t1]++;
                rd[t2]++;
                t1=find(t1),t2=find(t2);
                if(t1!=t2)pre[t1]=t2;
            }
            int cnt1=0,cnt2=0;
            for(int i=1;i<=n;i++)
            {
               if(pre[i]==i)cnt1++;
               if(rd[i] & 1)cnt2++;
            }
            if(cnt1==1 && (cnt2==2 || cnt2==0))flag=1;
            else flag=0;
            puts(flag?"Full":"Part");
        }
        return 0;
    }