Deque<Integer> makeEulerianCircuit(Deque<Integer>[] edges)
{
 // return empty list for empty graph
 if (edges.length==0)
 return new LinkedList<>(); //empty graph
 // Stack for the path in the current iteration
 Deque<Integer> currentPath = new ArrayDeque<>();
 // queue for the final circuit
 Deque<Integer> circuit = new ArrayDeque<>();
 // start from any vertex
 currentPath.push(0);
 int currentVertexNumber = 0; // Current vertex
 while (!currentPath.isEmpty())
 {
 if (edges[currentVertexNumber].size() > 0)
 {
 currentPath.push(currentVertexNumber);
 Deque<Integer> currentVertex = edges[currentVertexNumber];
 int nextVertexNumber = currentVertex.pop();
 currentVertexNumber = nextVertexNumber;
 }
 else
 {
 circuit.add(currentVertexNumber);
 currentVertexNumber = currentPath.pop();
 }
 }
 return circuit;
}

Is there anything that can make this faster? Better data structures? A more efficient algorithm? Right now it's not passing the assignment I'm writing it for, and I can't think of anything to make it work more efficiently.

import java.util.*;
class PrintCircuit{
 /**
 *
 * @param edges list of adjacent vertices for current edges
 * @return circuit in deque list
 */
 Deque<Integer> makeEulerianCircuit(Deque<Integer>[] edges, int numberOfNodes)
{
 // return empty list for empty graph
 if (edges.length==0)
 return new LinkedList<>(); //empty graph
 // Stack for the path in the current iteration
 Deque<Integer> currentPath = new ArrayDeque<>();
 // queue for the final circuit
 Deque<Integer> circuit = new ArrayDeque<>();
 // start from any vertex
 currentPath.push(0);
 int currentVertexNumber = 0; // Current vertex
 while (!currentPath.isEmpty())
 {
 //if there are outgoing edges
  if (edges[currentVertexNumber].size() > 0)
 {
 currentPath.push(currentVertexNumber);
 int nextVertexNumber = edges[currentVertexNumber].pop();
 currentVertexNumber = nextVertexNumber;
 }
 
 // otherwise step back
 else
 {
 circuit.add(currentVertexNumber);
 currentVertexNumber = currentPath.pop();
 }
 }
 return circuit;
 }
 public static void main(String[] args)
 {
 PrintCircuit pc = new PrintCircuit();
 pc.inputAndPrintCircuit();
 }
 /**
 * Get the input, check to make sure the graph is even and run the printCircuit function
 */
 private void inputAndPrintCircuit(){
 Scanner scanner = new Scanner(System.in);
 int[] in = new int[2];
 in[0] = scanner.nextInt();
 in[1] = scanner.nextInt();
 Deque<Integer>[] edges = new Deque[in[0]];
 for(int i=0;i<in[0];i++)
 {
 edges[i] = new ArrayDeque<>();
 }
 
 // evenChecker is a Nx2 array where [0] = incoming edges and [1] = outgoing edges
 //should be equal or graph isn't Eulerian
 int[][] evenChecker = new int[in[0]][2];
 for (int i = 0; i < in[1]; i++) {
 int from = scanner.nextInt()-1;
 int to = scanner.nextInt()-1;
 evenChecker[from][0]++;
 evenChecker[to][1]++;
 edges[from].push(to);
 }
 if(!isGraphEven(evenChecker)){
 System.out.println("0");
 System.exit(0);
 } else {
 System.out.println("1");
 }
 Deque<Integer> circuit = makeEulerianCircuit(edges, in[0]);
 while(circuit.size()>1){
 int nextNode = circuit.pollLast()+1;
 System.out.print(nextNode + " ");
 }
 System.out.println();
 }
 /**
 * checks to make sure that incoming edges = outgoing edges
 * @param evenChecker a Nx2 array where [0] = incoming edges and [1] = outgoing edges
 * @return true if incoming eges = outgoing edges, false otherwise
 */
 private boolean isGraphEven(int[][] evenChecker){
 for(int[] evenCheck:evenChecker){
 if(evenCheck[0]!=evenCheck[1]){
 return false;
}
 }
 return true;
 }
}

Is there anything that can make this faster? Better data structures? A more efficient algorithm? Right now it's not passing the assignment I'm writing it for, and I can't think of anything to make it work more efficiently.

Update: Here are the specifications of the assignment:

Task. Given a directed graph, find an Eulerian cycle in the graph or report that none exists.

Input Format. The first line contains integers n and m — the number of vertices and the number of edges, respectively. Each of the following m lines specifies an edge in the format "u v". (As usual, we assume that the vertices of the graph are {1, 2, . . . , n}.) The graph may contain self-loops (that is, edges of the form (v, v)) and parallel edges (that is, several copies of the same edge). It is guaranteed that the graph is strongly connected.

Constraints. 1 ≤ n ≤ 104 ; n ≤ m ≤ 105 ; 1 ≤ u, v ≤ n.

Output Format. If the graph has no Eulerian cycle, output 0. Otherwise output 1 in the first line and a sequence v1, v2, . . . , vm of vertices in the second line. This sequence should traverse an Eulerian cycle in the graph: (v1, v2),(v2, v3), . . . ,(vm−1, vm),(vm, v1) should all be edges of the graph and each edge of the graph should appear in this sequence exactly once. As usual, the graph may contain many Eulerian cycles (in particular, each Eulerian cycle may be traversed starting from any of its vertices). You may output any one of them.

Here is some sample input: Input:

3 4

2 3

2 2

1 2

3 1

Output:

1

1 2 2 3

I've also updated the above to include the entire program.

This method draws an Eulerian Circuit from a directed graph. The graph is represented by an array of Deques representing outgoing edges. It does not have to be Deques if there is a more efficient data type; as far as I can tell the Deque is the most efficient implementation of a stack but I could be wrong.

I've tried replacing the ArrayDeques with LinkedLists but it doesn't make any difference.

I've tried keeping an array edgeCount rather than checking the number of nodes using edges[currentVertexNumber].size() > 0. But that makes it slower.

Deque<Integer> makeEulerianCircuit(Deque<Integer>[] edges)
{
 // return empty list for empty graph
 if (edges.length==0)
 return new LinkedList<>(); //empty graph
 // Stack for the path in the current iteration
 Deque<Integer> currentPath = new ArrayDeque<>();
 // queue for the final circuit
 Deque<Integer> circuit = new ArrayDeque<>();
 // start from any vertex
 currentPath.push(0);
 int currentVertexNumber = 0; // Current vertex
 while (!currentPath.isEmpty())
 {
 if (edges[currentVertexNumber].size() > 0)
 {
 currentPath.push(currentVertexNumber);
 Deque<Integer> currentVertex = edges[currentVertexNumber];
 int nextVertexNumber = currentVertex.pop();
 currentVertexNumber = nextVertexNumber;
 }
 else
 {
 circuit.add(currentVertexNumber);
 currentVertexNumber = currentPath.pop();
 }
 }
 return circuit;
}

Is there anything that can make this faster? Better data structures? A more efficient algorithm? Right now it's not passing the assignment I'm writing it for, and I can't think of anything to make it work more efficiently.

This method draws an Eulerian Circuit from a directed graph. The graph is represented by an array of Deques representing outgoing edges. It does not have to be Deques if there is a more efficient data type; as far as I can tell the Deque is the most efficient implementation of a stack but I could be wrong.

I've tried replacing the ArrayDeques with LinkedLists but it doesn't make any difference.

I've tried keeping an array edgeCount rather than checking the number of nodes using edges[currentVertexNumber].size() > 0. But that makes it slower.

Deque<Integer> makeEulerianCircuit(Deque<Integer>[] edges)
{
 // return empty list for empty graph
 if (edges.length==0)
 return new LinkedList<>(); //empty graph
 // Stack for the path in the current iteration
 Deque<Integer> currentPath = new ArrayDeque<>();
 // queue for the final circuit
 Deque<Integer> circuit = new ArrayDeque<>();
 // start from any vertex
 currentPath.push(0);
 int currentVertexNumber = 0; // Current vertex
 while (!currentPath.isEmpty())
 {
 if (edges[currentVertexNumber].size() > 0)
 {
 currentPath.push(currentVertexNumber);
 Deque<Integer> currentVertex = edges[currentVertexNumber];
 int nextVertexNumber = currentVertex.pop();
 currentVertexNumber = nextVertexNumber;
 }
 else
 {
 circuit.add(currentVertexNumber);
 currentVertexNumber = currentPath.pop();
 }
 }
 return circuit;
}

Is there anything that can make this faster? Better data structures? A more efficient algorithm? Right now it's not passing the assignment I'm writing it for, and I can't think of anything to make it work more efficiently.