Monday, December 30, 2024
Google search engine
HomeData Modelling & AIPrint Nodes after level K from given node in Graph in ascending...
Data Modelling & AIData Structure & Algorithm

Print Nodes after level K from given node in Graph in ascending order

Ted Musemwa
By Ted Musemwa
0
3

Given an undirected graph, a source node src, and an integer K, the task is to print all nodes after level K from the source node in ascending orderĀ 
(nodes are from 1 to N ).

Examples:

Input: { (1, 2), (1, 3), (1, 4), (1, 5), (2, 10), (2, 4), (3, 8), (3, 9), (4, 11), (5, 6), (5, 7), (8, 12), (10, 13) }, K = 1, src = 1
Output: 6 7 8 9 10 11 12 13

under level 1 ā€“ 1, 2, 3, 4, 5

Input 2: {, (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9) }, K = 2, src = 4
Output: 1 7 8 9

under level 2 : 2, 3, 4, 5, 6

Approach: This can be solved with the following idea:

Using BFS, while moving across the neighboring element of src and maintaining levels in order to keep a count that we have crossed K. Once, K is crossed push the nodes data into a vector which will be returned as output.

Steps involved in the implementation of the above approach:

  • Make an adjacency list from the input.
  • Take a vector ans to store all nodes after level K.
  • Take a queue for BFS traversal.
  • Ā When we iterate the queue for more than K times it means that now nodes present in the queue lie after level K.
  • Take a visited array to check whether the particular node is previously visited or not.
  • Take a top element of the queue and rest on that node and add every neighbor node of that particular node into the queue.
  • At last sort the ans array and print all elements.

Below is the code for the implementation of the above approach:

C++




// C++ code for above approach
#include <bits/stdc++.h>
using namespace std;
Ā 
vector<int> afterLevelK(int src, int k, vector<int> adj[],
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā int n)
{
Ā 
Ā Ā Ā Ā // Create a visited array to check the
Ā Ā Ā Ā // particular node is previously
Ā Ā Ā Ā // visited or not
Ā Ā Ā Ā vector<int> vis(n + 1, 0);
Ā 
Ā Ā Ā Ā // Take queue for BFS traversal
Ā Ā Ā Ā queue<int> q;
Ā 
Ā Ā Ā Ā // Ans vector to store all element
Ā Ā Ā Ā // lies after level k
Ā Ā Ā Ā vector<int> ans;
Ā 
Ā Ā Ā Ā // Push src node into queue and
Ā Ā Ā Ā // mark it as visited
Ā Ā Ā Ā q.push(src);
Ā Ā Ā Ā vis[src] = 1;
Ā 
Ā Ā Ā Ā // Traverse graph
Ā Ā Ā Ā while (!q.empty()) {
Ā Ā Ā Ā Ā Ā Ā Ā int n = q.size();
Ā Ā Ā Ā Ā Ā Ā Ā while (n--) {
Ā 
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // Take top element of queue
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // and pop it
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā int top = q.front();
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā q.pop();
Ā 
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // If element lies after level
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // k then push it in ans vector
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (k < 0) {
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā ans.push_back(top);
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }
Ā 
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // Rest on node and check
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // its neighbour nodes
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā for (auto x : adj[top]) {
Ā 
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // If adjacent node is
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // not visited then mark
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // it as visited and
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // push it into queue
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (!vis[x]) {
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā q.push(x);
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā vis[x] = 1;
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }
Ā Ā Ā Ā Ā Ā Ā Ā }
Ā 
Ā Ā Ā Ā Ā Ā Ā Ā // Decrement the level
Ā Ā Ā Ā Ā Ā Ā Ā k--;
Ā Ā Ā Ā }
Ā 
Ā Ā Ā Ā return ans;
}
Ā 
// Drivers code
int main()
{
Ā 
Ā Ā Ā Ā // Total number of nodes
Ā Ā Ā Ā int n = 9;
Ā 
Ā Ā Ā Ā // All links in undirected graph
Ā Ā Ā Ā vector<pair<int, int> > links
Ā Ā Ā Ā Ā Ā Ā Ā = { { 1, 2 }, { 2, 3 }, { 3, 4 }, { 4, 5 },
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā { 5, 6 }, { 6, 7 }, { 7, 8 }, { 8, 9 } };
Ā 
Ā Ā Ā Ā // Adjacency list
Ā Ā Ā Ā vector<int> adj[n + 1];
Ā 
Ā Ā Ā Ā // Create graph in form of
Ā Ā Ā Ā // adjacency list
Ā Ā Ā Ā for (auto it : links) {
Ā Ā Ā Ā Ā Ā Ā Ā int u = it.first;
Ā Ā Ā Ā Ā Ā Ā Ā int v = it.second;
Ā 
Ā Ā Ā Ā Ā Ā Ā Ā adj[u].push_back(v);
Ā Ā Ā Ā Ā Ā Ā Ā adj[v].push_back(u);
Ā Ā Ā Ā }
Ā 
Ā Ā Ā Ā // Source node
Ā Ā Ā Ā int src = 4;
Ā 
Ā Ā Ā Ā // Level
Ā Ā Ā Ā int k = 2;
Ā 
Ā Ā Ā Ā // Function call
Ā Ā Ā Ā vector<int> ans = afterLevelK(src, k, adj, n);
Ā 
Ā Ā Ā Ā // sort ans vector
Ā Ā Ā Ā sort(ans.begin(), ans.end());
Ā 
Ā Ā Ā Ā // Traverse and print ans vector
Ā Ā Ā Ā for (auto it : ans) {
Ā Ā Ā Ā Ā Ā Ā Ā cout << it << " ";
Ā Ā Ā Ā }
Ā 
Ā Ā Ā Ā return 0;
}
 

















Java


















 






 




 



























// Java code for above approach


Ā 


import java.io.*;


import java.util.*;


Ā 


class GFG {


Ā 


Ā Ā Ā Ā static List<Integer>


Ā Ā Ā Ā afterLevelK(int src, int k, ArrayList<Integer>[] adj,


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā int n)


Ā Ā Ā Ā {


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā // Create a visited array to check whether the


Ā Ā Ā Ā Ā Ā Ā Ā // particular node is previously visited or not


Ā Ā Ā Ā Ā Ā Ā Ā boolean[] vis = new boolean[n + 1];


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā // Take a queue for BFS traversal


Ā Ā Ā Ā Ā Ā Ā Ā Queue<Integer> q = new LinkedList<>();


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā // Ans list to store all elements lies after level k


Ā Ā Ā Ā Ā Ā Ā Ā List<Integer> ans = new ArrayList<>();


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā // Push src node into queue and mark it as visited


Ā Ā Ā Ā Ā Ā Ā Ā q.offer(src);


Ā Ā Ā Ā Ā Ā Ā Ā vis[src] = true;


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā // Traverse graph


Ā Ā Ā Ā Ā Ā Ā Ā while (!q.isEmpty()) {


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā int len = q.size();


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā while (len-- > 0) {


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // Take top element of queue and poll it


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā int top = q.poll();


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // If element lies after level k then add it


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // in ans list


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (k < 0) {


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā ans.add(top);


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // Rest on node and check its neighbor nodes


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā for (int x : adj[top]) {


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // If adjacent node is not visited then


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // mark it as visited and add it into


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // queue


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (vis[x] == false) {


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā q.add(x);


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā vis[x] = true;


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // Decrement the level


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā k--;


Ā Ā Ā Ā Ā Ā Ā Ā }


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā return ans;


Ā Ā Ā Ā }


Ā 


Ā Ā Ā Ā public static void main(String[] args)


Ā Ā Ā Ā {


Ā Ā Ā Ā Ā Ā Ā Ā // Total number of nodes


Ā Ā Ā Ā Ā Ā Ā Ā int n = 9;


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā // All links in undirected graph


Ā Ā Ā Ā Ā Ā Ā Ā int[][] links


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā = { { 1, 2 }, { 2, 3 }, { 3, 4 }, { 4, 5 },


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā { 5, 6 }, { 6, 7 }, { 7, 8 }, { 8, 9 } };


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā // Adjacency list


Ā Ā Ā Ā Ā Ā Ā Ā ArrayList<Integer>[] adj = new ArrayList[n + 1];


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā for (int i = 1; i <= n; i++) {


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā adj[i] = new ArrayList<>();


Ā Ā Ā Ā Ā Ā Ā Ā }


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā // create graph in form of adjaceny list


Ā Ā Ā Ā Ā Ā Ā Ā for (int[] link : links) {


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā int u = link[0];


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā int v = link[1];


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā adj[u].add(v);


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā adj[v].add(u);


Ā Ā Ā Ā Ā Ā Ā Ā }


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā // source node


Ā Ā Ā Ā Ā Ā Ā Ā int src = 4;


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā // level


Ā Ā Ā Ā Ā Ā Ā Ā int k = 2;


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā // Function call


Ā Ā Ā Ā Ā Ā Ā Ā List<Integer> ans = afterLevelK(src, k, adj, n);


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā // sort the ans arraylist


Ā Ā Ā Ā Ā Ā Ā Ā Collections.sort(ans);


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā // traverse and print ans vector


Ā Ā Ā Ā Ā Ā Ā Ā for (int it : ans) {


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā System.out.print(it + " ");


Ā Ā Ā Ā Ā Ā Ā Ā }


Ā Ā Ā Ā }


}


Ā 


// This code is contributed by lokesh.








































Python3


















 






 




 



























from collections import deque


Ā 


Ā 


def after_level_k(src, k, adj, n):


Ā Ā Ā Ā # Create a visited array to check if the


Ā Ā Ā Ā # particular node is previously visited or not


Ā Ā Ā Ā vis = [False] * (n + 1)


Ā 


Ā Ā Ā Ā # Take a queue for BFS traversal


Ā Ā Ā Ā q = deque()


Ā 


Ā Ā Ā Ā # Ans list to store all elements


Ā Ā Ā Ā # that lie after level k


Ā Ā Ā Ā ans = []


Ā 


Ā Ā Ā Ā # Push src node into queue and


Ā Ā Ā Ā # mark it as visited


Ā Ā Ā Ā q.append(src)


Ā Ā Ā Ā vis[src] = True


Ā 


Ā Ā Ā Ā # Traverse graph


Ā Ā Ā Ā while q:


Ā Ā Ā Ā Ā Ā Ā Ā n = len(q)


Ā Ā Ā Ā Ā Ā Ā Ā while n > 0:


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # Take the top element of queue


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # and pop it


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā top = q.popleft()


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # If element lies after level k


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # then append it to ans list


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if k < 0:


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā ans.append(top)


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # Rest on node and check


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # its neighbour nodes


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā for x in adj[top]:


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # If adjacent node is not visited


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # then mark it as visited and


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # append it to queue


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if not vis[x]:


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā q.append(x)


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā vis[x] = True


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā n -= 1


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā # Decrement the level


Ā Ā Ā Ā Ā Ā Ā Ā k -= 1


Ā 


Ā Ā Ā Ā return ans


Ā 


Ā 


# Driver code


if __name__ == "__main__":


Ā Ā Ā Ā # Total number of nodes


Ā Ā Ā Ā n = 9


Ā 


Ā Ā Ā Ā # All links in undirected graph


Ā Ā Ā Ā links = [(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9)]


Ā 


Ā Ā Ā Ā # Adjacency list


Ā Ā Ā Ā adj = [[] for _ in range(n+1)]


Ā 


Ā Ā Ā Ā # Create graph in form of adjacency list


Ā Ā Ā Ā for u, v in links:


Ā Ā Ā Ā Ā Ā Ā Ā adj[u].append(v)


Ā Ā Ā Ā Ā Ā Ā Ā adj[v].append(u)


Ā 


Ā Ā Ā Ā # Source node


Ā Ā Ā Ā src = 4


Ā 


Ā Ā Ā Ā # Level


Ā Ā Ā Ā k = 2


Ā 


Ā Ā Ā Ā # Function call


Ā Ā Ā Ā ans = after_level_k(src, k, adj, n)


Ā 


Ā Ā Ā Ā # Sort ans list


Ā Ā Ā Ā ans.sort()


Ā 


Ā Ā Ā Ā # Traverse and print ans list


Ā Ā Ā Ā for it in ans:


Ā Ā Ā Ā Ā Ā Ā Ā print(it, end=" ")








































C#


















 






 




 



























using System;


using System.Collections.Generic;


using System.Linq;


Ā 


class Program {


Ā Ā Ā Ā static List<int> AfterLevelK(int src, int k,


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā List<int>[] adj, int n)


Ā Ā Ā Ā {


Ā Ā Ā Ā Ā Ā Ā Ā // Create a visited array to check if


Ā Ā Ā Ā Ā Ā Ā Ā // a particular node is previously visited or not


Ā Ā Ā Ā Ā Ā Ā Ā bool[] vis = new bool[n + 1];


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā // Take queue for BFS traversal


Ā Ā Ā Ā Ā Ā Ā Ā Queue<int> q = new Queue<int>();


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā // Ans list to store all elements


Ā Ā Ā Ā Ā Ā Ā Ā // that lie after level k


Ā Ā Ā Ā Ā Ā Ā Ā List<int> ans = new List<int>();


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā // Push src node into queue and mark it as visited


Ā Ā Ā Ā Ā Ā Ā Ā q.Enqueue(src);


Ā Ā Ā Ā Ā Ā Ā Ā vis[src] = true;


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā // Traverse graph


Ā Ā Ā Ā Ā Ā Ā Ā while (q.Count > 0) {


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā int count = q.Count;


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā while (count-- > 0) {


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // Take top element of queue and dequeue it


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā int top = q.Dequeue();


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // If element lies after level k, then add


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // it to ans list


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (k < 0) {


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā ans.Add(top);


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // Visit adjacent nodes and push them into


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // queue if not visited


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā foreach(int x in adj[top])


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā {


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (!vis[x]) {


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā q.Enqueue(x);


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā vis[x] = true;


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // Decrement the level


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā k--;


Ā Ā Ā Ā Ā Ā Ā Ā }


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā return ans;


Ā Ā Ā Ā }


Ā 


Ā Ā Ā Ā static void Main(string[] args)


Ā Ā Ā Ā {


Ā Ā Ā Ā Ā Ā Ā Ā // Total number of nodes


Ā Ā Ā Ā Ā Ā Ā Ā int n = 9;


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā // All links in undirected graph


Ā Ā Ā Ā Ā Ā Ā Ā Tuple<int, int>[] links = new Tuple<int, int>[] {


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Tuple.Create(1, 2), Tuple.Create(2, 3),


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Tuple.Create(3, 4), Tuple.Create(4, 5),


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Tuple.Create(5, 6), Tuple.Create(6, 7),


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Tuple.Create(7, 8), Tuple.Create(8, 9)


Ā Ā Ā Ā Ā Ā Ā Ā };


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā // Adjacency list


Ā Ā Ā Ā Ā Ā Ā Ā List<int>[] adj = new List<int>[ n + 1 ];


Ā Ā Ā Ā Ā Ā Ā Ā for (int i = 0; i <= n; i++) {


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā adj[i] = new List<int>();


Ā Ā Ā Ā Ā Ā Ā Ā }


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā // Create graph in form of adjacency list


Ā Ā Ā Ā Ā Ā Ā Ā foreach(Tuple<int, int> it in links)


Ā Ā Ā Ā Ā Ā Ā Ā {


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā int u = it.Item1;


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā int v = it.Item2;


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā adj[u].Add(v);


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā adj[v].Add(u);


Ā Ā Ā Ā Ā Ā Ā Ā }


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā // Source node


Ā Ā Ā Ā Ā Ā Ā Ā int src = 4;


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā // Level


Ā Ā Ā Ā Ā Ā Ā Ā int k = 2;


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā // Function call


Ā Ā Ā Ā Ā Ā Ā Ā List<int> ans = AfterLevelK(src, k, adj, n);


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā // Sort ans list


Ā Ā Ā Ā Ā Ā Ā Ā ans.Sort();


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā // Traverse and print ans list


Ā Ā Ā Ā Ā Ā Ā Ā foreach(int it in ans) { Console.Write(it + " "); }


Ā Ā Ā Ā }


}








































Javascript


















 






 




 



























function afterLevelK(src, k, adj, n) {


Ā Ā Ā Ā // Create a visited array to check whether


Ā Ā Ā Ā // a particular node is previously visited or not


Ā Ā Ā Ā const vis = new Array(n + 1).fill(0);


Ā 


Ā Ā Ā Ā // Take a queue for BFS traversal


Ā Ā Ā Ā const q = [];


Ā 


Ā Ā Ā Ā // Ans array to store all elements


Ā Ā Ā Ā // that lie after level k


Ā Ā Ā Ā const ans = [];


Ā 


Ā Ā Ā Ā // Push the src node into the queue and


Ā Ā Ā Ā // mark it as visited


Ā Ā Ā Ā q.push(src);


Ā Ā Ā Ā vis[src] = 1;


Ā 


Ā Ā Ā Ā // Traverse the graph


Ā Ā Ā Ā while (q.length !== 0) {


Ā Ā Ā Ā Ā Ā Ā Ā const levelSize = q.length;


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā for (let i = 0; i < levelSize; i++) {


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // Take the top element of the queue


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // and remove it from the queue


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā const top = q.shift();


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // If the element lies after level k,


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // then push it into the ans array


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (k < 0) {


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā ans.push(top);


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // Explore the neighbours of the current node


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā for (let j = 0; j < adj[top].length; j++) {


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā const neighbour = adj[top][j];


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // If the adjacent node is not visited,


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // then mark it as visited and push it into the queue


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (!vis[neighbour]) {


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā q.push(neighbour);


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā vis[neighbour] = 1;


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }


Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }


Ā Ā Ā Ā Ā Ā Ā Ā }


Ā 


Ā Ā Ā Ā Ā Ā Ā Ā // Decrement the level


Ā Ā Ā Ā Ā Ā Ā Ā k--;


Ā Ā Ā Ā }


Ā 


Ā Ā Ā Ā return ans;


}


Ā 


// Driver code


(function main() {


Ā Ā Ā Ā // Total number of nodes


Ā Ā Ā Ā const n = 9;


Ā 


Ā Ā Ā Ā // All links in undirected graph


Ā Ā Ā Ā const links = [


Ā Ā Ā Ā Ā Ā Ā Ā [1, 2],


Ā Ā Ā Ā Ā Ā Ā Ā [2, 3],


Ā Ā Ā Ā Ā Ā Ā Ā [3, 4],


Ā Ā Ā Ā Ā Ā Ā Ā [4, 5],


Ā Ā Ā Ā Ā Ā Ā Ā [5, 6],


Ā Ā Ā Ā Ā Ā Ā Ā [6, 7],


Ā Ā Ā Ā Ā Ā Ā Ā [7, 8],


Ā Ā Ā Ā Ā Ā Ā Ā [8, 9]


Ā Ā Ā Ā ];


Ā 


Ā Ā Ā Ā // Adjacency list


Ā Ā Ā Ā const adj = new Array(n + 1).fill().map(() => []);


Ā 


Ā Ā Ā Ā // Create the graph in the form of


Ā Ā Ā Ā // an adjacency list


Ā Ā Ā Ā for (const [u, v] of links) {


Ā Ā Ā Ā Ā Ā Ā Ā adj[u].push(v);


Ā Ā Ā Ā Ā Ā Ā Ā adj[v].push(u);


Ā Ā Ā Ā }


Ā 


Ā Ā Ā Ā // Source node


Ā Ā Ā Ā const src = 4;


Ā 


Ā Ā Ā Ā // Level


Ā Ā Ā Ā const k = 2;


Ā 


Ā Ā Ā Ā // Function call


Ā Ā Ā Ā const ans = afterLevelK(src, k, adj, n);


Ā 


Ā Ā Ā Ā // Sort ans array


Ā Ā Ā Ā ans.sort((a, b) => a - b);


Ā 


Ā Ā Ā Ā // Traverse and print ans array


Ā Ā Ā Ā console.log(ans.join(' '));


})();










































Output


1 7 8 9 




Time Complexity: O (V+E)
Auxiliary Space: O (V)







                                            Feeling lost in the world of random DSA topics, wasting time without progress? Itā€™s time for a change! Join our DSA course, where weā€™ll guide you on an exciting journey to master DSA efficiently and on schedule.

                                            Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!





Commit to GfGā€™s Three-90 Challenge! Purchase a course, complete 90% in 90 days, and save 90% cost click here to explore.





Last Updated : 

20 Apr, 2023




Like Article






Save Article














Previous



<!– 


8 Min Read | Java


 –>



Querying frequency of elements in a range








Next





<!– 


8 Min Read | Java


 –>



What is Binary Search Algorithm?










Share your thoughts in the comments

















































Previous article
JavaScript Math.atanh() Function
Next article
How to Declare & Initialise a String in different Programming languages?



Ted Musemwa
Ted Musemwa


RELATED ARTICLES











Most Popular
Load more


Recent Comments


	

ź°•ģ„œźµ¬ģ¶œģž„ė§ˆģ‚¬ģ§€ on How to store XML data into a MySQL database using Python?
	
 

	

źøˆģ²œźµ¬ģ¶œģž„ė§ˆģ‚¬ģ§€ on How to store XML data into a MySQL database using Python?
	
 

	

nightwish.southeast.cz on Google says it won’t keep your Pixel during a repair if you’re caught using non-OEM parts
	
 

	

ź“‘ėŖ…ģ¶œģž„ģ•ˆė§ˆ on How to store XML data into a MySQL database using Python?
	
 

	

ź“‘ėŖ…ģ¶œģž„ģ•ˆė§ˆ on How to store XML data into a MySQL database using Python?
	
 

	

ģ¶œģž„ģ˜¤ķ”¼ on How to store XML data into a MySQL database using Python?
	
 

	

ė¶€ģ²œģ¶œģž„ģ•ˆė§ˆ on How to store XML data into a MySQL database using Python?
	
 

	

źµ¬ģ›”ė™ģ¶œģž„ģ•ˆė§ˆ on How to store XML data into a MySQL database using Python?
	
 

	

ź°•ģ„œźµ¬ģ¶œģž„ģ•ˆė§ˆ on How to store XML data into a MySQL database using Python?
	
 

	

ķ—¬ė”œģ¶œģž„ on How to store XML data into a MySQL database using Python?
	
 

	

ģ˜¤ģ‚°ģ¶œģž„ģ•ˆė§ˆ on How to store XML data into a MySQL database using Python?
	
 

	

ź“‘ėŖ…ģ¶œģž„ė§ˆģ‚¬ģ§€ on How to store XML data into a MySQL database using Python?
	
 

	

ė§ˆķ¬ģ¶œģž„ on How to store XML data into a MySQL database using Python?
	
 

	

ģ•ˆģ–‘ģ¶œģž„ė§ˆģ‚¬ģ§€ on How to store XML data into a MySQL database using Python?
	
 

	

gKTdhA on 5 reasons why I won’t switch away from Google Photos
	
 

	

ė¶€ģ²œģ¶œģž„ģ•ˆė§ˆ on How to store XML data into a MySQL database using Python?
	
 

	

ė™ķƒ„ģ¶œģž„ģ•ˆė§ˆ on How to store XML data into a MySQL database using Python?
	
 

	

0a1Mq7 on Wander: An add-on for Appleā€™s Shortcuts app to install the Odyssey jailbreak
	
 

	

ģ„œģšøģ¶œģž„ģ•ˆė§ˆ on How to store XML data into a MySQL database using Python?
	
 

	

ė¶„ė‹¹ģ¶œģž„ģ•ˆė§ˆ on How to store XML data into a MySQL database using Python?
	
 

	

ė¶€ģ²œģ¶œģž„ģ•ˆė§ˆ on How to store XML data into a MySQL database using Python?
	
 

	

ģ¶œģž„ ģ˜¤ķ”¼ on How to store XML data into a MySQL database using Python?
	
 

	

ķ™”ź³”ė™ģ¶œģž„ė§ˆģ‚¬ģ§€ on How to store XML data into a MySQL database using Python?
	
 

	

Gilda on Wander: An add-on for Appleā€™s Shortcuts app to install the Odyssey jailbreak
	
 

	

ź°•ģ„œźµ¬ģ¶œģž„ė§ˆģ‚¬ģ§€ on How to store XML data into a MySQL database using Python?
	
 

	

ź³ ģ–‘ģ¶œģž„ģ•ˆė§ˆ on How to store XML data into a MySQL database using Python?
	
 

	

ķ™”ģ„±ģ¶œģž„ė§ˆģ‚¬ģ§€ on How to store XML data into a MySQL database using Python?
	
 

	

ģ²œķ˜øė™ģ¶œģž„ė§ˆģ‚¬ģ§€ on How to store XML data into a MySQL database using Python?
	
 

	

June P. D. Alvarez on RedSn0w Updated to Fix iBooks DRM Issues
	
 

	

Litha on How to Install Siri on iPad 2
	
 
 
                                    

            

        

        
    
 


    

                

            














EDITOR PICKS





POPULAR POSTS





POPULAR CATEGORY










 







ABOUT US



Newspaper is your news, entertainment, music fashion website. We provide you with the latest breaking news and videos straight from the entertainment industry.



Contact us: hello@geeksforgeeks.org






FOLLOW US











© Lazyr0ar 2022