Hamiltonian Path And Cycle

I/O:

7

9

0 1 10

1 2 10

2 3 10

0 3 10

3 4 10

4 5 10

5 6 10

4 6 10

2 5 10

0

O/P:

0123456.

0123465.

0125643*

0346521*

0123456.

0123465.

0125643*

0346521*

Hamiltonian Path

    - visit all vertices

    - don't visit any vertice twice

Hamiltonian Cycle

    - first and last vertices should have direct connection

Method 1. USING BOOLEAN visited AND counter (print . at the end)

Method 2. USING HASHSET visited AND counter (print * at the end)

package pep.Day39;

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

public class Hamiltonian_Path_And_Cycle {

    static class Edge {
        int src;
        int nbr;
        int wt;

        Edge(int src, int nbr, int wt) {
            this.src = src;
            this.nbr = nbr;
            this.wt = wt;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int vtces = Integer.parseInt(br.readLine());
        ArrayList<Edge>[] graph = new ArrayList[vtces];
        for (int i = 0; i < vtces; i++) {
            graph[i] = new ArrayList<>();
        }

        int edges = Integer.parseInt(br.readLine());
        for (int i = 0; i < edges; i++) {
            String[] parts = br.readLine().split(" ");
            int v1 = Integer.parseInt(parts[0]);
            int v2 = Integer.parseInt(parts[1]);
            int wt = Integer.parseInt(parts[2]);
            graph[v1].add(new Edge(v1, v2, wt));
            graph[v2].add(new Edge(v2, v1, wt));
        }

        int src = Integer.parseInt(br.readLine());

        // write all your codes here
        boolean[] visited1 = new boolean[vtces];
        hamiltonianPathAndCycle1(graph, src, visited1, "", vtces - 1, src);

        System.out.println();

        HashSet visited2 = new HashSet();
        hamiltonianPathAndCycle2(graph, src, visited2, "", src);
    }

    // USING HASHSET visited AND counter

    private static void hamiltonianPathAndCycle2(ArrayList<Edge>[] graph, int src, HashSet visited2, String asf, int firstSource) {
        if (visited2.size() == graph.length - 1) {
            asf += src;
            System.out.print(asf);
            for (Edge e : graph[firstSource]) {
                if (e.nbr == src) {
                    System.out.println("*");
                    return;
                }
            }
            System.out.println(".");
            return;
        }

        visited2.add(src);
        asf += src;
        for (Edge e : graph[src]) {
            if (!visited2.contains(e.nbr)) {
                hamiltonianPathAndCycle2(graph, e.nbr, visited2, asf, firstSource);
            }
        }
        visited2.remove(src);
    }

    // USING BOOLEAN visited AND counter
    private static void hamiltonianPathAndCycle1(ArrayList<Edge>[] graph, int src, boolean[] visited, String asf, int count, int firstSource) {
        if (count == 0) {
            asf += src;
            System.out.print(asf);

            for (Edge e : graph[firstSource]) {
                if (e.nbr == src) {
                    System.out.println("*");
                    return;
                }
            }
            System.out.println(".");
            return;
        }

        visited[src] = true;
        asf += src;
        for (Edge e : graph[src]) {
            if (!visited[e.nbr]) {
                hamiltonianPathAndCycle1(graph, e.nbr, visited, asf, count - 1, firstSource);
            }
        }
        visited[src] = false;

    }


}