Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #from sortedcontainers import SortedList
- # cook your dish here
- from collections import defaultdict
- g=defaultdict(set)
- #n=int(input())
- deg=defaultdict(int)
- n=int(input())
- e=int(input())
- for i in range(e):
- a=int(input())
- b=int(input())
- g[a].add(b)
- g[b].add(a)
- deg[a]+=1
- deg[b]+=1
- #print(g)
- #print(deg)
- def get_key(val):
- for k, v in deg.items():
- if v==val:
- return k
- ans=0
- while deg:
- #print("hey")
- #print(deg)
- ans+=1
- max_deg=max(deg.values())
- key=get_key(max_deg)
- deg.pop(key)
- for v in g[key]:
- if v not in g:
- continue
- deg[v]-=1
- if deg[v]<=0:
- deg.pop(v)
- print(ans)
Advertisement
Add Comment
Please, Sign In to add comment