Hamilton Cycle

    public static void HamiltonCycle(int n, int m, boolean directed,
                                     int nodei[], int nodej[], int cycle[]) {
        int i, j, k, stacklen, lensol, stackindex, len, len1, len2, low, up;
        int firstedges[] = new int[n + 2];
        int endnode[] = new int[m + m + 1];
        int stack[] = new int[m + m + 1];
        boolean connect[] = new boolean[n + 1];
        boolean join, skip;

        // set up the forward star representation of the graph
        k = 0;

        for (i = 1; i <= n; i++) {
            firstedges[i] = k + 1;

            for (j = 1; j <= m; j++) {
                if (nodei[j] == i) {
                    k++;

                    endnode[k] = nodej[j];
                }

                if (!directed) {
                    if (nodej[j] == i) {
                        k++;

                        endnode[k] = nodei[j];
                    }
                }
            }
        }

        firstedges[n + 1] = k + 1;

        // initialize
        lensol = 1;
        stacklen = 0;

        // find the next node
        while (true) {
            if (lensol == 1) {
                stack[1] = 1;
                stack[2] = 1;
                stacklen = 2;
            } else {
                len1 = lensol - 1;
                len2 = cycle[len1];

                for (i = 1; i <= n; i++) {
                    connect[i] = false;
                    low = firstedges[len2];
                    up = firstedges[len2 + 1];

                    if (up > low) {
                        up--;

                        for (k = low; k <= up; k++) {
                            if (endnode[k] == i) {
                                connect[i] = true;

                                break;
                            }
                        }
                    }
                }

                for (i = 1; i <= len1; i++) {
                    len = cycle[i];
                    connect[len] = false;
                }

                len = stacklen;
                skip = false;

                if (lensol != n) {
                    for (i = 1; i <= n; i++) {
                        if (connect[i]) {
                            len++;

                            stack[len] = i;
                        }
                    }

                    stack[len + 1] = len - stacklen;
                    stacklen = len + 1;
                } else {
                    for (i = 1; i <= n; i++) {
                        if (connect[i]) {
                            if (!directed) {
                                if (i > cycle[2]) {
                                    stack[len + 1] = len - stacklen;
                                    stacklen = len + 1;
                                    skip = true;

                                    break;
                                }
                            }

                            join = false;
                            low = firstedges[i];
                            up = firstedges[i + 1];

                            if (up > low) {
                                up--;

                                for (k = low; k <= up; k++) {
                                    if (endnode[k] == 1) {
                                        join = true;

                                        break;
                                    }
                                }
                            }

                            if (join) {
                                stacklen += 2;
                                stack[stacklen - 1] = i;
                                stack[stacklen] = 1;
                            } else {
                                stack[len + 1] = len - stacklen;
                                stacklen = len + 1;
                            }

                            skip = true;

                            break;
                        }
                    }

                    if (!skip) {
                        stack[len + 1] = len - stacklen;
                        stacklen = len + 1;
                    }
                }
            }

            // search further
            while (true) {
                stackindex = stack[stacklen];

                stacklen--;

                if (stackindex == 0) {
                    lensol--;

                    if (lensol == 0) {
                        cycle[0] = 1;

                        return;
                    }

                    continue;
                } else {
                    cycle[lensol] = stack[stacklen];
                    stack[stacklen] = stackindex - 1;

                    if (lensol == n) {
                        cycle[0] = 0;

                        return;
                    }

                    lensol++;

                    break;
                }
            }
        }
    }