public abstract class HamiltonianCycle {

    /**
     * Initialiseer een verzameling die alle toppen bevat van een graaf g.
     * @param n het aantal toppen van g
     * @return de verzameling als bitset
     */
    public abstract long initialize(int n);

    /**
     * Voeg een top aan een verzameling toe.
     * @param set de verzameling
     * @param v de top
     * @return de nieuwe verzameling
     */
    public abstract long add(long set, int v);

    /**
     * Verwijder een top uit een verzameling.
     * @param set de verzameling
     * @param v de top
     * @return de nieuwe verzameling
     */
    public abstract long remove(long set, int v);

    /**
     * Controleer of er een top in g bestaat die niet in het pad zit en minder dan twee buren niet in het midden van het pad heeft.
     * @param g voor elke top v is g[v] een bitset met de buren van v
     * @param niet_midden_pad verzameling van toppen die niet in het midden van het pad zitten
     * @param in_pad verzameling van toppen in het pad
     * @return true als er zo een top bestaat
     */
    public abstract boolean bound(long[] g, long niet_midden_pad, long in_pad);

    public final boolean hasHamiltonianCycle(long[] g) {
        long niet_midden_pad = initialize(g.length);
        for (int start = 0; start < g.length; start++) {
            if (findHamiltonianCycle(g, niet_midden_pad, 1L << start, start, start)) {
                return true;
            }
        }
        return false;
    }

    private boolean findHamiltonianCycle(long[] g, long niet_midden_pad, long in_pad, int start, int end) {
        if (in_pad == initialize(g.length)) {
            return (g[end] & (1L << start)) != 0;
        }

        if (!bound(g, niet_midden_pad, in_pad)) {
            if (start != end) niet_midden_pad = remove(niet_midden_pad, end);
            for (long buren = g[end] & ~in_pad; buren != 0; buren = buren & (buren - 1)) {
                int v = Long.numberOfTrailingZeros(buren);
                if (findHamiltonianCycle(g, niet_midden_pad, add(in_pad, v), start, v)) {
                    return true;
                }
            }
        }

        return false;
    }
}