Advertisement
Iam_Sandeep

M coloring graph backtracking

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