# Exercise8 (HW8)
###### tags: `2020pdsa`

Judge Open: 2021/1/19
This is just an exercise. This score is **NOT included** into our final score.

[toc]

## Version
Python: 3.8.5 (Note: no numpy)
Java: openjdk14 (https://openjdk.java.net/projects/jdk/14/)
Platform: Debian

## Our Judge
https://c4lab.bime.ntu.edu.tw:13000

Grading Status:
* AC: ACcepted
* TLE: Time Limit Excess
* WA: Wrong Answer
* RE: Runtime Error (Mostly your program raise some error unexpectly)

Memory: 2G

Handin the file with utf-8 encoding if there are 中文 words inside your code (including comments).

# HW8 Euler Cycle
Given non-directed edges, try to find out Euler cyle in the graph.

We guarantee all of the nodes have even and positive degrees.

Output one of possible eulurcycle is fine.

## Hint
* DFS

## Template

import sys 
sys.setrecursionlimit(100001)

class Eulercycle:
    def eulercycle(self, num_node: int, edges: list[int]) -> List[int] :
        return [0,1,2]


def toEdge(a):
    return [[min(a[i-1:i+1]), max(a[i-1:i+1])] for i in range(1, len(a))]


if __name__ == "__main__":
    edges = [[0,1],[1,2],[0,2]]
    path = Eulercycle().eulercycle(3, edges)
    # [0, 2, 1, 0]
    print(len(path) == len(edges) + 1 and
          sorted(toEdge(path)) == sorted([[min(i), max(i)] for i in edges]))

    edges = [[0,1],[1,2],[0,2], [1,3],[1,4], [3,4]]
    path = Eulercycle().eulercycle(5, edges)
    # [0, 2, 1, 3, 4, 1, 0]
    print(len(path) == len(edges) + 1 and
          sorted(toEdge(path)) == sorted([[min(i), max(i)] for i in edges]))

    edges = [[0,1],[1,2],[0,2], [1,4],[1,3], [3,4]]
    path = Eulercycle().eulercycle(5, edges)
    # [0, 2, 1, 3, 4, 1, 0]
    print(len(path) == len(edges) + 1 and
          sorted(toEdge(path)) == sorted([[min(i), max(i)] for i in edges]))

    edges = [[0,1],[1,2],[0,2], [0,4],[0,3], [3,4]]
    path = Eulercycle().eulercycle(5, edges)
    # [0, 3, 4, 0, 2, 1, 0]
    print(len(path) == len(edges) + 1 and
          sorted(toEdge(path)) == sorted([[min(i), max(i)] for i in edges]))

    edges = [[0,1],[1,2],[0,2], [0,3],[0,4], [3,4]]
    path = Eulercycle().eulercycle(5, edges)
    # [0, 3, 4, 0, 2, 1, 0]
    print(len(path) == len(edges) + 1 and
          sorted(toEdge(path)) == sorted([[min(i), max(i)] for i in edges]))
    
    edges = [[0,1],[1,2],[0,2], [0,0]]
    path = Eulercycle().eulercycle(3, edges)
    # [0, 0, 2, 1, 0]
    print(len(path) == len(edges) + 1 and
          sorted(toEdge(path)) == sorted([[min(i), max(i)] for i in edges]))

java template

import java.util.List;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.Queue;
import java.util.Stack;
import java.util.Comparator;
import java.lang.Math;


class Eulercycle {
    public Eulercycle() {};

    public int[] eulercycle(int num_node, int[][] edges) {
        return new int[]{0,1,2,0};
    }

    public boolean check(int[] path, int[][] edges) {
        if(path.length != edges.length + 1)
            return false;

        int[][] output_edges = new int[path.length - 1][2];
        for(int i=0; i<path.length-1; ++i) {
            output_edges[i][0] = Math.min(path[i], path[i+1]);
            output_edges[i][1] = Math.max(path[i], path[i+1]);
        }
        Arrays.sort(output_edges, (a, b) -> Arrays.compare(a,b));
        Arrays.sort(edges, (a, b) -> Arrays.compare(a,b));

        for(int i=0;i<path.length-1; ++i)
            if(!Arrays.equals(output_edges[i], edges[i]))
                return false;
        return true;
    }

    public static void main(String[] args) {
        Eulercycle m = new Eulercycle();
        int[][] edges = new int[][]{ {0,1}, {1,2}, {0,2} };
        int[] path = m.eulercycle(3, edges);
        // 0 1 2 0
        System.out.println(m.check(path, edges));
        
        // copy the testcase from python template by yourself
        // .. feel free to edit in HackMD
    }
}


## TestCase

Cases
* case1: 20 points: nodes <= 5, edges < 10
* case2: 20 points: nodes <= 10, edges < 500
* case3: 30 points: nodes <= 100, edges < 5000
* case4: 30 points: nodes <= 1000, edges < 50000

## Time Limit
(We can extend it if needed)
I don't want to set strict time limit on this problem
Python: 10s
Java: 3s

## Modified from
109-1 PDSA Final Example Problem 2