Solution Idea

50111. Hamiltonian Cycle

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <stdio.h>
#define maxn 1000
int adj[maxn][maxn];
void printsol(int sol[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", sol[i]);
    printf("0\n");
    return;
}
int mcl(int n, int pick, int pick_n, int sol[maxn], int picked[maxn]) {
    if (pick_n == n) {
        if (adj[pick][0] == 1) {
            printsol(sol, n);
            return 1;
        }
        else return 0;
    }
    for (int i = 0; i < n; i++) {
        if (!picked[i] && adj[pick][i]) {
            sol[pick_n] = i;
            picked[i] = 1;
            if (mcl(n , i, pick_n+1, sol, picked) )
                return 1;
            picked[i] = 0;
        }
    }
    return 0;
}
int main() {
    int n, e;
    scanf("%d%d", &n, &e);
    while(e--) {
        int x, y;
        scanf("%d%d", &x, &y);
        adj[x][y] = 1;
        adj[y][x] = 1;
    }
    int sol[maxn] ={}, picked[maxn] = {};
    sol[0] = 0;
    picked[0] = 1;
    if (!mcl(n, 0, 1, sol, picked))
        printf("NO SOLUTION\n");
    return 0;
}

Discussion