Given an undirected graph consisting of N nodes labeled from 0 to N – 1, which are represented by a 2D array arr[][], where arr[i] represents all the nodes that are connected to the ith node, the task is to find whether we can visit all the nodes from node X.
Examples:
Input: arr = { { 1, 2 }, { 0, 3, 2 }, {0, 1}, {1} }, N = 4, X = 0
Output: YES
Explanation: As can be seen from the below graph, we can reach to any node from node 0.
The structure of the above graph
Input: arr = { { 1, 2 }, { 0, 3, 2 }, {0, 1}, {1} }, N = 5, X = 4
Output: NO
Explanation: No node is connected to the node 4.
An approach using BFS:
The idea is to use BFS from starting from node X and count all the nodes that are visited in the path. Finally check if number of nodes that are visited are equal to given number of node N or not. If they are equal then print YES, otherwise NO.
Follow the steps below to implement the above idea:
- The given array acts as n adjacency list of the graph.
- Initialize a queue and visited array, push start node X into a queue and mark it visited.
- Initialize a count variable to keep count of the number of nodes that are visited during BFS
- Do the following while queue size is greater than 0
- Pop the top node (say curr) node from the queue and increment the count by 1.
- Explore all the children of curr node
- Check if the children of the current node are visited, if not then push it into the queue and mark it visited.
- Finally, check if the count is equal to the given N,
- If true, print YES
- otherwise, print NO
Below is the implementation of the above approach.
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;// Function to find if// all nodes can be visited from Xbool canVisitAllNodes(vector<vector<int> >& arr, int X, int n){ queue<int> q; vector<int> visited(n, false); q.push(X); visited[X] = true; int count = 0; // Loop to implement BFS while (q.size() > 0) { int size = q.size(); for (int i = 0; i < size; i++) { auto curr = q.front(); q.pop(); count++; for (auto j : arr[curr]) { if (visited[j] == false) { q.push(j); visited[j] = true; } } } } // Check if all nodes are visited if (count == n) return true; return false;}// Driver codeint main(){ vector<vector<int> > arr = { { 1, 2 }, { 0, 3, 2 }, { 0, 1 }, { 1 } }; int N = 4, X = 0; // Function Call if (canVisitAllNodes(arr, X, N)) { cout << "YES" << endl; } else { cout << "NO" << endl; } return 0;} |
Java
// Java code for the above approach:import java.io.*;import java.util.*;class GFG { // Function to find if all nodes can be visited from X static boolean canVisitAllNodes(int[][] arr, int X, int n) { Queue<Integer> q = new LinkedList<>(); boolean[] visited = new boolean[n]; Arrays.fill(visited, Boolean.FALSE); q.add(X); visited[X] = true; int count = 0; // Loop to implement BFS while (q.size() > 0) { int size = q.size(); for (int i = 0; i < size; i++) { int curr = q.poll(); count++; for (var j : arr[curr]) { if (visited[j] == false) { q.add(j); visited[j] = true; } } } } // Check if all nodes are visited if (count == n) { return true; } return false; } public static void main(String[] args) { int[][] arr = { { 1, 2 }, { 0, 3, 2 }, { 0, 1 }, { 1 } }; int N = 4, X = 0; // Function call if (canVisitAllNodes(arr, X, N)) { System.out.println("YES"); } else { System.out.println("NO"); } }}// This code is contributed by lokeshmvs21. |
Python3
# Python code for the above approach:# Function to find if# all nodes can be visited from Xdef canVisitAllNodes(arr, X, n): q = [] visited = [False]*n q.append(X) visited[X] = True count = 0 # Loop to implement BFS while(len(q) > 0): size = len(q) for i in range(size): curr = q.pop(0) count = count + 1 for j in arr[curr]: if(visited[j] == False): q.append(j) visited[j] = True # Check if all nodes are visited if(count == n): return True return False # Driver codearr = [[1, 2], [0, 3, 2], [0, 1], [1]]N, X = 4, 0# Function Callif(canVisitAllNodes(arr, X, N)): print("YES")else: print("NO") # This code is contributed by Pushpesh Raj. |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;public class GFG { // Driver Code public static void Main(string[] args) { int[][] arr = new int[4][]; arr[0] = new int[] { 1, 2 }; arr[1] = new int[] { 0, 3, 2 }; arr[2] = new int[] { 0, 1 }; arr[3] = new int[] { 1 }; int n = 4, X = 0; Queue<int> q = new Queue<int>(); bool[] visited = new bool[n]; for (int i = 0; i < n; i++) { visited[i] = false; } q.Enqueue(X); visited[X] = true; int count = 0; // Loop to implement BFS while (q.Count > 0) { int size = q.Count; for (int i = 0; i < size; i++) { int curr = q.Dequeue(); count++; for (int k = 0; k < arr[curr].Length; k++) { int j = arr[curr][k]; if (visited[j] == false) { q.Enqueue(j); visited[j] = true; } } } } // Check if all nodes are visited if (count == n) { Console.Write("Yes"); } else { Console.Write("NO"); } }}// This code is contributed by garg28harsh. |
Javascript
// Javascript code for the above approach:// Function to find if// all nodes can be visited from Xfunction canVisitAllNodes(arr, X, n) { let q = []; let visited = new Array(n).fill(false); q.push(X); visited[X] = true; let count = 0; // Loop to implement BFS while (q.length > 0) { let size = q.length; for (let i = 0; i < size; i++) { let curr = q.shift(); count++; for (let j of arr[curr]) { if (visited[j] == false) { q.push(j); visited[j] = true; } } } } // Check if all nodes are visited if (count == n) return true; return false;}// Driver codevar arr = [ [ 1, 2 ], [ 0, 3, 2 ], [ 0, 1 ], [ 1 ] ];var N = 4, X = 0;// Function Callif (canVisitAllNodes(arr, X, N)) { console.log("YES");}else { console.log("NO");}// This code is contributed by Tapesh(tapeshdua420) |
Output
YES
Time Complexity: O(N + E) where N is the number of nodes and E is the number of edges.
Auxiliary Space: O(N)
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!
