Iam_Sandeep

Untitled

Aug 28th, 2022
1,152
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.76 KB | None | 0 0
  1.  
  2. #from sortedcontainers import SortedList
  3. # cook your dish here
  4. from collections import  defaultdict
  5. g=defaultdict(set)
  6. #n=int(input())
  7. deg=defaultdict(int)
  8.  
  9. n=int(input())
  10. e=int(input())
  11. for i in range(e):
  12.     a=int(input())
  13.     b=int(input())
  14.     g[a].add(b)
  15.     g[b].add(a)
  16.     deg[a]+=1
  17.     deg[b]+=1
  18. #print(g)
  19. #print(deg)
  20.  
  21.  
  22. def get_key(val):
  23.     for k, v in deg.items():
  24.         if v==val:
  25.             return k
  26. ans=0
  27.  
  28. while deg:
  29.     #print("hey")
  30.     #print(deg)
  31.     ans+=1
  32.     max_deg=max(deg.values())
  33.     key=get_key(max_deg)
  34.     deg.pop(key)
  35.     for v in g[key]:
  36.         if v not in g:
  37.             continue
  38.              
  39.         deg[v]-=1
  40.         if deg[v]<=0:
  41.             deg.pop(v)
  42.            
  43. print(ans)
  44.  
  45.    
  46.    
  47.  
  48.  
Advertisement
Add Comment
Please, Sign In to add comment