目录

 

---

1 问题描述

Problem Description

欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个图，问是否存在欧拉回路？

 

Input

测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是节点数N ( 1 < N < 1000 )和边数M；随后的M行对应M条边，每行给出一对正整数，分别是该条边直接连通的两个节点的编号（节点从1到N编号）。当N为0时输入结

束。

 

Output

每个测试用例的输出占一行，若欧拉回路存在则输出1，否则输出0。

 

Sample Input

3 3

1 2

1 3

2 3

3 2

1 2

2 3

0

 

Sample Output

1

0

 

 

 

---

2 解决方案

具体代码如下：

package com.liuzhen.practice;import java.util.ArrayList;import java.util.Scanner;public class Main {    public static int MAX = 1000;    public static int[][] map = new int[MAX][MAX];      //输入图    public static ArrayList
     
       result = new ArrayList
      
       ();  //用于存放最终输出结果        //判断给定图的每个顶点的度是否均为偶数    public boolean judge(int[] degree) {        for(int i = 0;i < degree.length;i++) {            if(degree[i] % 2 != 0)                return false;        }        return true;    }        //使用BFS遍历，判断给定图是否为连通图    public boolean bfs(int n) {        boolean[] used = new boolean[n];        ArrayList
       
         list = new ArrayList
        
         ();        list.add(0);        used[0] = true;        while(!list.isEmpty()) {            int temp = list.get(0);            list.remove(0);            for(int i = 0;i < n;i++) {                if(!used[i] && map[temp][i] != 0) {                    used[i] = true;                    list.add(i);                }            }        }        for(int i = 0;i < n;i++) {            if(used[i] == false)                return false;        }        return true;    }        public static void main(String[] args) {        Main test = new Main();        Scanner in = new Scanner(System.in);        while(true) {            int n = in.nextInt();       //输入图的顶点数            if(n == 0)                break;            int m = in.nextInt();       //输入图的边数目            int[] degree = new int[n];   //用于计算输入图的每个顶点的度            for(int i = 0;i < m;i++) {                int a = in.nextInt();                int b = in.nextInt();                map[a - 1][b - 1] = 1;                map[b - 1][a - 1] = 1;                degree[a - 1]++;                degree[b - 1]++;            }            if(test.judge(degree) && test.bfs(n))                result.add(1);            else                result.add(0);        }        for(int i = 0;i < result.size();i++)            System.out.println(result.get(i));    }}
        
       
      
     

 

运行结果：

3 31 21 32 33 21 22 3010

 

 

 

 

 

参考资料：

   1.