REC-Design-and-Analysis-of-Algorithm-DAA-Digital-Cafe/Backtracking/PP1-Hamiltonian-Cycle.c at main · CrypticFate5/REC-Design-and-Analysis-of-Algorithm-DAA-Digital-Cafe · GitHub

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <stdio.h>
#include <string.h>

int help(int k, int n, int *vis, int c, int graph[][n])
{
    if (c == n - 1)
    {
        if (graph[k][0] == 1)
        {
            int l = 0;
            for (int i = 0; i < n; i++)
            {
                if (vis[i] != -1)
                    l++;
            }
            if (l == n)
            {
                return 1;
            }
        }
        return 0;
    }
    for (int i = 0; i < n; i++)
    {
        if (vis[i] == -1 && graph[k][i] == 1)
        {
            if (k == 0)
                vis[k] = 0;
            c++;
            vis[i] = c;
            if (help(i, n, vis, c, graph))
                return 1;
            c--;
            vis[i] = -1;
        }
    }
    return 0;
}
int main()
{
    int n;
    scanf("%d", &n);
    int graph[n][n];
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            scanf("%d", &graph[i][j]);
        }
    }
    int vis[n];
    memset(vis, -1, sizeof(vis));
    int path[n];
    int j = 0;
    if (help(0, n, vis, 0, graph))
    {
        printf("The hamiltonian cycle is ");
        for (int i = 0; i < n; i++)
        {
            path[vis[i]] = j;
            j++;
        }
        for (int i = 0; i < n; i++)
        {
            printf("%d ", path[i]);
        }
        printf("0");
    }
    else
    {
        printf("The hamiltonian cycle does not exist");
    }
    return 0;
}