We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
# Enter your code here. Read input from STDIN. Print output to STDOUTQ=int(input().strip())neighbors={}weights=[]defflood_fill(x,vis):vis.add(x)foryinneighbors[x]:ifnotyinvis:flood_fill(y,vis)returnvisdefcompute_indep(graph,curr,n):ifn==len(graph):returnsum(map(lambdax:weights[x],curr))elifweights[graph[n]]==0:returncompute_indep(graph,curr,n+1)ans=compute_indep(graph,curr,n+1)x=graph[n]possible=Trueforyincurr:ifyinneighbors[x]:possible=Falsebreakifpossible:ans=max(ans,compute_indep(graph,curr+[x],n+1))returnansforiinrange(Q):query=input().strip()ifquery[0]=='A':weights.append(int(query[1:]))neighbors[len(weights)-1]=set()elifquery[0]=='B':x,y=map(int,query[1:].split())neighbors[x-1].add(y-1)neighbors[y-1].add(x-1)else:#'C'component=list(flood_fill(int(query[1:])-1,set()))weights.append(compute_indep(component,[],0))neighbors[len(weights)-1]=set()forxincomponent:weights[x]=0neighbors[x]=set()counted=set()ans=0foriinrange(len(weights)):ifweights[i]>0andinotincounted:component=list(flood_fill(i,set()))forxincomponent:counted.add(x)ans+=compute_indep(component,[],0)print(ans)
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Zurikela's Graph
You are viewing a single comment's thread. Return to all comments →
Python3 solution