#1176 : 欧拉路·一（欧拉通路的判定）

╰半夏微凉° 2023-07-08 09:17 30阅读 0赞

# \#1176 : 欧拉路·一 #

时间限制:10000ms
    单点时限:1000ms
    内存限制:256MB

描述  
小Hi和小Ho最近在玩一个解密类的游戏，他们需要控制角色在一片原始丛林里面探险，收集道具，并找到最后的宝藏。现在他们控制的角色来到了一个很大的湖边。湖上有N个小岛(编号1…N)，以及连接小岛的M座木桥。每座木桥上各有一个宝箱，里面似乎装着什么道具。

湖边还有一个船夫，船夫告诉主角。他可以载着主角到任意一个岛上，并且可以从任意一个岛上再载着主角回到湖边，但是主角只有一次来回的机会。同时船夫告诉主角，连接岛屿之间的木桥很脆弱，走过一次之后就会断掉。

因为不知道宝箱内有什么道具，小Hi和小Ho觉得如果能把所有的道具收集齐肯定是最好的，那么对于当前岛屿和木桥的情况，能否将所有道具收集齐呢？

举个例子，比如一个由6个小岛和8座桥组成的地图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RiX3lvdXRo_size_16_color_FFFFFF_t_70]

主角可以先到达4号小岛，然后按照4->1->2->4->5->6->3->2->5的顺序到达5号小岛，然后船夫到5号小岛将主角接回湖边。这样主角就将所有桥上的道具都收集齐了。

提示：欧拉路的判定

输入  
第1行：2个正整数，N,M。分别表示岛屿数量和木桥数量。1≤N≤10,000，1≤M≤50,000

第2…M+1行：每行2个整数，u,v。表示有一座木桥连接着编号为u和编号为v的岛屿，两个岛之间可能有多座桥。1≤u,v≤N

输出  
第1行：1个字符串，如果能收集齐所有的道具输出“Full”，否则输出”Part”。

样例输入  
6 8  
1 2  
1 4  
2 4  
2 5  
2 3  
3 6  
4 5  
5 6  
样例输出  
Full

# 涉及到的知识点： #

1.  欧拉通路定义：通过图（无向图或有向图）中**所有边一次且仅一次 行遍所有的顶点**的 **通路**称作**欧拉通路**。
2.  欧拉回路的定义：通过图中**所有边一次且仅一次行遍所有顶点**的**回路**称为**欧拉回路**。
3.  欧拉图：具有**欧拉回路 的 图**称为**欧拉图**。
4.  半欧拉图：具有**欧拉通路 的 图**称为**半欧拉图**。
5.  规定平凡图【1阶零图【一条边也没有】】为欧拉图。
6.  定理1：**无向图**是**欧拉图** 当且仅当它是**连通图**且**没有奇度顶点**。
7.  定理2：**无向图**是**半欧拉图** 当且仅当它是**连通图**且**恰有2个奇度顶点**。

# 思路： #

判断欧拉通路：判断它是否为欧拉图或半欧拉图即可。

本题是无向图，认真读题，它给的一定是连通图（所以无需判断连通性），所以根据上述定理1和2只需要统计奇度顶点个数即可。

# AC代码： #

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <algorithm>
    using namespace std;
    const int N = 1e4+5;
    int d[N];
    /*
    struct Edge
    {
        int from;
        int to;
        int nxt;
    }edge[N*5];
    int head[N],idx;
    bool vis[N];
    int total;
    void init()
    {
        memset(head,-1,sizeof(head));
        idx = 0;
    }
    void add_edge(int from,int to)
    {
        edge[idx].from = from;
        edge[idx].to = to;
        edge[idx].nxt = head[from];
        head[from] = idx++;
    }
    void dfs(int s)
    {
        for(int i = head[s]; ~i; i = edge[i].nxt)
        {
            int to = edge[i].to;
            if(!vis[to])
            {
                vis[to] = true;
                total++;
                dfs(to);
            }
        }
    }
    */
    int main()
    {
        
        int n,m;
        scanf("%d%d",&n,&m);
        //init();
        while(m--)
        {
        
            int x,y;
            scanf("%d%d",&x,&y);
            d[x]++;
            d[y]++;
            //add_edge(x,y);
            //add_edge(y,x);
        }
        int cnt = 0;
        for(int i = 1; i <= n; i++)
        {
        
            cnt += d[i] & 1;
        }
        bool flag = false;
        if(cnt == 0 || cnt == 2)
        {
        
            /*
            vis[1] = true;
            total = 1;
            dfs(1);*/
            flag = true;
        }
        flag?puts("Full"):puts("Part");
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RiX3lvdXRo_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200225215006792.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RiX3lvdXRo,size_16,color_FFFFFF,t_70