The Flight Plan - 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. And we have use dictionary named "dd" in which we store its parent node if we print that dictionary we get the path for for each node from source given node.

For the Problem goto below link and search for problem: The Flight Plan

Code :

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]*100 dd=defaultdict(list) dd[s].append(0) visited = [False] * 100#(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 dd[i].append(s) for j in dd[s]: dd[i].append(j) queue.append(i) visited[i] = True print(dist[l]+1) return dd[l] def main(): 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]) l3=list(map(int,input().split())) ans=g.BFS(l3[0],l3[1]) ans.reverse() for i in ans: if i==0: continue print(i,end=' ') print(l3[1],end=' ') main()

Social Networking Graph - 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. And then we see count nodes which are at a given distance from given source node.

For the Problem goto below link and search for problem: Social Networking Graph

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,a): dist=[0]*100 visited = [False] * 100#(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.count(a) def main(): ml=[] 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 n=int(input()) for j in range(n): ll=list(map(int,input().split())) ans=g.BFS(ll[0],ll[1]) ml.append(ans) for i in ml: print(i) main()

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()