GRAPH COLOURING

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

def graph_coloring_util(graph, m, color, v, n):
    if v == n:
        return True  #returns true if all vertices are coloured

    for c in range(1, m + 1):
        if is_safe(graph, v, c, color, n):
            color[v] = c
            if graph_coloring_util(graph, m, color, v + 1, n): #recursively calls for next vertex
                return True  #valid coloring was found
            color[v] = 0  #function backtracks

def graph_coloring(graph, m):
    n = len(graph)  
    color = [0] * n  #array is initialized set to 0 indicating no vertices are coloured initially'
   
    if not graph_coloring_util(graph, m, color, 0, n):  #initially set to 0
        return None

    return color

n = int(input("Enter the number of vertices in the graph: "))
print("Enter the adjacency matrix (0 or 1) for the graph:")
graph = []
for i in range(n):
    row = list(map(int, input().split()))
    graph.append(row)

m = int(input("Enter the number of colors: "))

result = graph_coloring(graph, m)
if result is not None:
    print("Graph Coloring Result:", result)
else:
    print(f"No solution found with {m} colors.")