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 9under 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 codeint 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 approachimport 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 dequedef 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 codeif __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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
