Advertisement
Iam_Sandeep

Untitled

May 14th, 2022 (edited)
732
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. def graphColoring(graph, k, n):
  2.     vis={}
  3.     adj={i:[] for i in range(n)}
  4.    
  5.     for i in range(n):
  6.         for j in range(n):
  7.             if graph[i][j]==1:
  8.                 adj[i].append(j)
  9.              
  10.    
  11.     def possible(v,i):
  12.         for ver in adj[v]:
  13.             if ver in vis and vis[ver]==i:
  14.                 return False
  15.         return True
  16.    
  17.     def dfs(u):
  18.         if u==n:return True
  19.         for i in range(k):
  20.             if possible(u,i):
  21.                 vis[u]=k
  22.                 if dfs(u+1):return True
  23.                 vis.pop(u)
  24.         return False
  25.     if dfs(0):return 1
  26.     else:return 0
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement