Monk and the Islands - Hackerearth Problem Solution Using Python

Here , To solve this problem we have use the BFS algorithm using python in which we just add a "dist" list in which we store distance of every node from its parent node.

For the Problem goto below link and search for problem: Monk and Islands

Code :

from collections import defaultdict from collections import defaultdict class Graph: def __init__(self): self.graph = defaultdict(list) def addEdge(self,u,v): self.graph[u].append(v) def BFS(self, s,l): dist=[0]*10000000 visited = [False] * 10000000#(len(self.graph)+1) queue = [] queue.append(s) visited[s] = True while queue: s = queue.pop(0) for i in self.graph[s]: if visited[i] == False: dist[i]=dist[s]+1 #this is the dist list queue.append(i) visited[i] = True return dist[l[0]] def main(): t=int(input()) ml=[] for i in range(t): l=list(map(int,input().split())) g=Graph() for i in range(l[1]): l2=list(map(int,input().split())) g.addEdge(l2[0],l2[1]) g.addEdge(l2[1],l2[0]) #graph is bidirectional ans=g.BFS(1,l) ml.append(ans) for i in ml: print(i) main()