题目详情

给出一个无向图，判断其是欧拉、半欧拉还是非欧拉图。

• 欧拉图：可以构成欧拉回路
• 半欧拉图：可以构成欧拉通路
• 非欧拉图：啥也不行

我的版本

没撕出来……卡死在判断通路上了。

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        int n = Integer.parseInt(line[0]) + 1; // 点数，点索引从1开始
        int m = Integer.parseInt(line[1]);     // 边数
        int[][] eds = new int[n][n];
        HashMap<Integer, Integer> hm = new HashMap<>();
        for (int i = 0; i < m; i ++) {
            line = br.readLine().split(" ");
            int x = Integer.parseInt(line[0]);
            int y = Integer.parseInt(line[1]);
            eds[x][y] = eds[y][x] = 1;         // 无向图
            int count;
            count = hm.computeIfAbsent(x, k->0);
            hm.put(x, count+1);
            count = hm.computeIfAbsent(y, k->0);
            hm.put(y, count+1);
        }
        for (int i = 1; i < n; i ++) {
            if (i == 1) System.out.print(hm.get(i));
            else System.out.print(" "+hm.get(i));
        }
        System.out.println();
        int isPrint = 0;
        for (int k = 1; k < n; k ++) {
            // 从索引为1的点开始，最终可以到达所有的点，使用栈记录到过的点
            int[] bool = new int[n];
            Stack<Integer> st = new Stack<>();
            st.add(k);
            bool[k] = 1;
            while (st.size() != 0 && st.size() < n - 1) {
                int node = st.peek();
                int b = 0;
                for (int i = 1; i < n; i++) {
                    if (bool[i] == 0 && eds[node][i] == k) {
                        st.add(i);
                        b = 1;
                        break;
                    }
                }
                if (b == 0) {
                    st.pop();
                    if (st.size() != 0) eds[st.peek()][node] = k+1;
                } else {
                    bool[node] = 1;
                }
                if (st.size() == 0) {
                    System.out.println("Non-Eulerian");
                    isPrint = 1;
                } else if (st.size() == n - 1 && eds[st.peek()][1] == k) {
                    System.out.println("Eulerian");
                    isPrint = 1;
                }
            }
        }
        if (isPrint == 0) {
            System.out.println("Semi-Eulerian");
        }
    }
}

看了答案的版本

其实欧拉图是有规律的，学的离散喂狗了……欧拉图/半欧拉图首先是连通图（使用栈判断），在此基础上，

• 欧拉图：所有的点的度为偶数
• 半欧拉：只有两个点的度为奇数
• 非欧拉：其他

手撕的这个版本有一个节点超时了。

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        int n = Integer.parseInt(line[0]) + 1; // 点数，点索引从1开始
        int m = Integer.parseInt(line[1]);     // 边数
        int[][] eds = new int[n][n];
        int[] hm = new int[n];
        for (int i = 0; i < m; i ++) {
            line = br.readLine().split(" ");
            int x = Integer.parseInt(line[0]);
            int y = Integer.parseInt(line[1]);
            eds[x][y] = eds[y][x] = 1;         // 无向图
            hm[x] += 1;
            hm[y] += 1;
        }
        int[] bool = new int[n];
        Stack<Integer> st = new Stack<>();
        st.add(1);
        while (st.size() != 0) {
            int node = st.peek();
            bool[node] = 1;
            int b = 0;
            for (int i = 1; i < n; i++) {
                if (bool[i] == 0 && eds[node][i] == 1) {
                    st.add(i);
                    b = 1;
                    break;
                }
            }
            if (b == 0) st.pop();
        }
        int oddNum = 0;       // 奇度节点数目
        int isConnect = 1;    // 是否连通
        for (int i = 1; i < n; i ++) {
            if (hm[i] % 2 != 0) oddNum ++;
            if (bool[i] == 0) isConnect = 0;
            if (i == 1) System.out.print(hm[i]);
            else System.out.print(" "+hm[i]);
        }
        System.out.println();
        if (oddNum == 0 && isConnect == 1) System.out.println("Eulerian");
        else if (oddNum == 2 && isConnect == 1) System.out.println("Semi-Eulerian");
        else System.out.println("Non-Eulerian");
    }
}