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