(UVA) Hamiltonian Cycle - Solution

Link to the solution: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=716

The solution below used Backtracking to try to find a Hamiltonian Cycle.


import java.io.*;
import java.util.*;

class Main {
    public ArrayList<ArrayList<Integer>> adjList;
    public HashSet<Integer> visited;
    public ArrayList<Integer> orderVisit;
    public ArrayList<Integer> answer;
    public int numVertices;
    public boolean found;
    public int start;
   
    public void rec(int curr) {
        if (visited.size() == numVertices && adjList.get(curr).contains(start)) {
            answer = (ArrayList<Integer>) orderVisit.clone();
            answer.add(start);
            found = true;
            return;
        }
       
        ArrayList<Integer> reachVertices = adjList.get(curr);
        for (int i = 0; i < reachVertices.size(); i++) {
            if (found) {
                return;
            }
            if (visited.contains(reachVertices.get(i))) {
                continue;
            }
            visited.add(reachVertices.get(i));
            orderVisit.add(reachVertices.get(i));
            rec(reachVertices.get(i));
            orderVisit.remove(orderVisit.size()-1);
            visited.remove(reachVertices.get(i));
        }
    }
   
    public void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
       
        while (sc.hasNext()) {
            numVertices = sc.nextInt();
           
            adjList = new ArrayList<>();
            for (int i = 0; i <= numVertices; i++) {
                adjList.add(new ArrayList<Integer>());
            }
           
            String n = sc.next();
            while (!n.equals("%")) {
                int n1 = Integer.parseInt(n);
                int n2 = sc.nextInt();
                adjList.get(n1).add(n2);
                adjList.get(n2).add(n1);
               
                n = sc.next();
            }
           
            found = false;
            answer = new ArrayList<>();
            orderVisit = new ArrayList<>();
            visited = new HashSet<>();
            visited.add(1);
            orderVisit.add(1);
            start = 1;
            rec(1);
           
            if (answer.size() > 0) {
                for (int i = 0; i < answer.size(); i++) {
                    if (i == answer.size()-1) {
                        bw.write(answer.get(i)+"\n");
                        break;
                    }
                    bw.write(answer.get(i)+" ");
                }
            } else {
                bw.write("N\n");
            }
           
        }  
                                              
        bw.flush();
        bw.close();
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}