欧拉路径（连通）

题目描述 在图论中，欧拉路径是图中的一条路径，适合每边一次。

欧拉回路是在同一顶点开始和结束的欧拉路径。

它们最早是欧拉于 1736 在解决著名的哥尼斯堡七桥问题时提出。

事实证明，如果连个连通图的所有顶点都是偶数，那么这个连通图就有欧拉回路，这个图就叫欧拉图。

如果一个连接图中有两个顶点的度数为奇数，而其他顶点的度数为偶数，那么所有的欧拉路径都从一个度数为奇数的顶点开始，并在另一个度数为奇数的顶点结束。

欧拉路径但没有欧拉回路的图片被称为半欧拉图。

现在，给出一个无向图，请判断它是欧拉图、半欧拉图还是非欧拉图。

输入格式 第一行包含两个整数 N 和 M，表示无向图的点和边数。

接下来 M 行，每行包含两个整数 a,b，表示点 a 和 b 有一边。

从所有点的编号 1～N。

输出格式 首先，在第一行按顺序输出点 1～N 每个点的度数。

第二行输出判断图，Eulerian(欧拉图)，Semi-Eulerian(半欧拉图)，Non-Eulerian(非欧拉图)。

行尾不得有多余的空间。

数据范围 1≤N≤500, 1≤M≤N(N?1)2

样例 输入样例1： 7 12 5 7 1 2 1 3 2 3 2 4 3 4 5 2 7 6 6 3 4 5 6 4 5 6 输出样例1： 2 4 4 4 4 4 2 Eulerian 输入样例2： 6 10 1 2 1 3 2 3 2 4 3 4 5 2 6 3 4 5 6 4 5 6 输出样例2： 2 4 4 4 3 3 Semi-Eulerian 输入样例3： 5 8 1 2 2 5 5 4 4 1 1 3 3 2 3 4 5 3 输出样例3： 3 3 4 3 3 Non-Eulerian

思路一： 搜索 枚举 记录连通点数cnt是否为n,再按题目要求来 Eulerian(欧拉图)，Semi-Eulerian(半欧拉图)，Non-Eulerian(非欧拉图) 连通点数为n 没有完全连接，但有欧拉路径 除上述要求外

时间复杂度 参考文献 C 代码

#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 1010; int n,m,res; int d[N]; bool st[N],g[N][N]; int dfs(int u) {     st[u]=1;     int cnt=1;     for (int i = 1; i <= n; i    )       if(!st[i]&&g[u][i])cnt =dfs(i);//如果连接     return cnt; } int main() {     cin>>n>>m;     while (m -- )     {         int a,b;         cin>>a>>b;         g[a][b]=g[b][a]=true;         d[a]  ,d[b]  ;     }     int cnt=dfs(1);     for (int i = 1; i <= n; i    )cout<<d[i]<<' ';     puts("");     if(cnt==n)     {         for (int i = 1; i <= n; i    )            if(d[i]&1)res  ;         if(res==0)puts("Eulerian");         else if(res==2)puts("Semi-Eulerian");         else puts("Non-Eulerian");     }     else  puts("Non-Eulerian");     return 0; }

思路二： 并查集 枚举 并收集和判断连接

时间复杂度 O(n) 参考文献 C 代码

#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 1e6 10; int n,m,res,ret; int s[N],p[N]; int find(int x)   {    return p[x]==x?x:p[x]=find(p[x]); } int main() {     cin>>n>>m;     for (int i = 1; i <= n; i    )p[i]=i;     while (m -- )     {         int a,b,x,y;         cin>>a>>b;         x=find(a),y=find(b);         if(x!=y)p[x]=y;         s[a]  ,s[b]  ;     }     int x=find(1);     bool flag=false;     for (int i = 2; i <= n; i    )     {         int xx=find(i);         if(x!=xx)         {             flag=true;             break;//不连通         }     }     for (int i = 1; i <= n; i    )     {         if(s[i]&1)res  ;         else ret  ;         cout<<s[i]<<' ';     }     puts("");     if(flag)puts("Non-Eulerian");     else     {         if(res==0)puts("Eulerian");         else if(res==2)puts("Semi-Eulerian");         else puts("Non-Eulerian");     }     return 0; }

Java代码 最后一个数据（m==12345) TLE 不知道怎么修改，请大佬指教。

import java.io.*; import java.util.*; public class Main {     static int p[]=new int [1010];     static int s[]=new int [1010];     static int res=0;     public static int find(int x)     {         if (p[x] != x) p[x] = find(p[x]);         return p[x];     }     public static void main(String args[])  {         Scanner cin = new Scanner(System.in);         int n=cin.nextInt(),m=cin.nextInt();         for (int i = 1; i <= n; i    )p[i]=i;         while(m--!=0)         {             int a,b,x,y;             a=cin.nextInt();             b=cin.nextInt();             x=find(a);             y=find(b);             if(x!=y)p[x]=y;             s[a]  ;             s[b]  ;         }         int x=find(1);         boolean flag=false;         for (int i = 2; i <= n; i    )          {           int xx=find(i);           if(x!=xx)           {             flag=true;             break;//不连通           }         }         for (int i = 1; i <= n; i    )        {         if(s[i]%2!=0)res  ;         System.out.print(s[i] " ");        }        System.out.println("");       if(flag==true) System.out.println("Non-Eulerian);
      else
      {
        if(res==0) System.out.println("Eulerian");
        else if(res==2) System.out.println("Semi-Eulerian");
        else  System.out.println("Non-Eulerian");
      }
      return ;

    }
}

欢迎留言点赞