Graph Coloring and Hamiltonian Path: Backtracking on Graphs

def m_coloring(graph, m):
    n = len(graph)
    colors = [0] * n

    def is_safe(v, c):
        for u in range(n):
            if graph[v][u] and colors[u] == c:
                return False
        return True

    def bt(v):
        if v == n: return True
        for c in range(1, m + 1):
            if is_safe(v, c):
                colors[v] = c
                if bt(v + 1): return True
                colors[v] = 0
        return False

    return bt(0), colors

# Bipartite check (2-coloring)
def is_bipartite(graph):
    n = len(graph)
    color = [-1] * n
    def bt(v, c):
        color[v] = c
        for u in range(n):
            if graph[v][u]:
                if color[u] == c: return False
                if color[u] == -1 and not bt(u, 1-c): return False
        return True
    for v in range(n):
        if color[v] == -1 and not bt(v, 0):
            return False
    return True

# Hamiltonian Path (visit every vertex exactly once)
def hamiltonian_path(graph):
    n = len(graph)
    path = [0]  # start at vertex 0
    visited = [False] * n
    visited[0] = True

    def bt():
        if len(path) == n: return True
        last = path[-1]
        for next_v in range(n):
            if not visited[next_v] and graph[last][next_v]:
                visited[next_v] = True
                path.append(next_v)
                if bt(): return True
                path.pop()
                visited[next_v] = False
        return False

    return path if bt() else []

# Hamiltonian Cycle
def hamiltonian_cycle(graph):
    n = len(graph)
    path = [0]
    visited = [False] * n
    visited[0] = True

    def bt():
        if len(path) == n:
            return graph[path[-1]][0]  # can return to start?
        last = path[-1]
        for v in range(1, n):  # don't revisit start until end
            if not visited[v] and graph[last][v]:
                visited[v] = True
                path.append(v)
                if bt(): return True
                path.pop()
                visited[v] = False
        return False

    return path + [0] if bt() else []

#include <bits/stdc++.h>
using namespace std;

bool mColoring(vector<vector<int>>& graph, int m, vector<int>& colors, int v) {
    int n = graph.size();
    if (v == n) return true;
    for (int c = 1; c <= m; c++) {
        bool safe = true;
        for (int u = 0; u < n; u++)
            if (graph[v][u] && colors[u] == c) { safe = false; break; }
        if (safe) {
            colors[v] = c;
            if (mColoring(graph, m, colors, v+1)) return true;
            colors[v] = 0;
        }
    }
    return false;
}