Count nodes within K | Python3 program to count nodes inside K distance range from marked nodes ; Utility bfs method to fill distance vector and returns most distant marked node from node u ; push node u in queue and initialize its distance as 0 ; loop untill all nodes are processed ; if node is marked , update lastMarked variable ; loop over all neighbors of u and update their distance before pushing in queue ; if not given value already ; return last updated marked value ; method returns count of nodes which are in K - distance range from marked nodes ; vertices in a tree are one more than number of edges ; fill vector for graph ; fill boolean array mark from marked array ; vectors to store distances ; first bfs ( from any random node ) to get one distant marked node ; second bfs to get other distant marked node and also dl is filled with distances from first chosen marked node ; third bfs to fill dr by distances from second chosen marked node ; loop over all nodes ; increase res by 1 , if current node has distance less than K from both extreme nodes ; Driver Code
import queue NEW_LINE def bfsWithDistance ( g , mark , u , dis ) : NEW_LINE INDENT lastMarked = 0 NEW_LINE q = queue . Queue ( ) NEW_LINE q . put ( u ) NEW_LINE dis [ u ] = 0 NEW_LINE while ( not q . empty ( ) ) : NEW_LINE INDENT u = q . get ( ) NEW_LINE if ( mark [ u ] ) : NEW_LINE INDENT lastMarked = u NEW_LINE DEDENT for i in range ( len ( g [ u ] ) ) : NEW_LINE INDENT v = g [ u ] [ i ] NEW_LINE if ( dis [ v ] == - 1 ) : NEW_LINE INDENT dis [ v ] = dis [ u ] + 1 NEW_LINE q . put ( v ) NEW_LINE DEDENT DEDENT DEDENT return lastMarked NEW_LINE DEDENT def nodesKDistanceFromMarked ( edges , V , marked , N , K ) : NEW_LINE INDENT V = V + 1 NEW_LINE g = [ [ ] for i in range ( V ) ] NEW_LINE u , v = 0 , 0 NEW_LINE for i in range ( V - 1 ) : NEW_LINE INDENT u = edges [ i ] [ 0 ] NEW_LINE v = edges [ i ] [ 1 ] NEW_LINE g [ u ] . append ( v ) NEW_LINE g [ v ] . append ( u ) NEW_LINE DEDENT mark = [ False ] * V NEW_LINE for i in range ( N ) : NEW_LINE INDENT mark [ marked [ i ] ] = True NEW_LINE DEDENT tmp = [ - 1 ] * V NEW_LINE dl = [ - 1 ] * V NEW_LINE dr = [ - 1 ] * V NEW_LINE u = bfsWithDistance ( g , mark , 0 , tmp ) NEW_LINE u = bfsWithDistance ( g , mark , u , dl ) NEW_LINE bfsWithDistance ( g , mark , u , dr ) NEW_LINE res = 0 NEW_LINE for i in range ( V ) : NEW_LINE INDENT if ( dl [ i ] <= K and dr [ i ] <= K ) : NEW_LINE INDENT res += 1 NEW_LINE DEDENT DEDENT return res NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT edges = [ [ 1 , 0 ] , [ 0 , 3 ] , [ 0 , 8 ] , [ 2 , 3 ] , [ 3 , 5 ] , [ 3 , 6 ] , [ 3 , 7 ] , [ 4 , 5 ] , [ 5 , 9 ] ] NEW_LINE V = len ( edges ) NEW_LINE marked = [ 1 , 2 , 4 ] NEW_LINE N = len ( marked ) NEW_LINE K = 3 NEW_LINE print ( nodesKDistanceFromMarked ( edges , V , marked , N , K ) ) NEW_LINE DEDENT