Given a directed acyclic graph of N nodes, the task is to find the smallest set of vertices from which the complete graph can be visited.
Examples:
Input: Graph in the image below
Output: 0 4
Explanation: From vertex 0, the set of nodes that can be visited is {0 ,1}. Similarly, from vertex 4, {4, 3, 2} can be visited. Hence, the complete graph can be visited from the set {0, 4} which is of the minimum possible size.Input: Graph in the image below
Output: 3 4
Approach 1: The given problem can be solved using topological sorting to get the ordering of vertices such that for every directed edge from U to V, U comes before V. Below are the steps to follow:
- Sort the given array of vertices in topological order using Khan’s Algorithm.
- Maintain an array visited which keeps track of the visited vertices.
- Iterate the sorted array perform the following operations:
- If the current vertex is not visited, insert it into the required set.
- Visit all the nodes that are reachable from the inserted node using DFS traversal.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;class Solution { public: // Function to perform DFS void dfs(int node, unordered_set<int>& vis, map<int, vector<int> >& graph) { // add node to visited set vis.insert(node); for (int adj : graph[node]) { if (vis.count(adj) == 0) { dfs(adj, vis, graph); } } } vector<int> solve(vector<vector<int> >& edges) { map<int, vector<int> > graph; // dictionary storing // indegrees of node map<int, int> indeg; // array to store topological // sorting of the array vector<int> topo_sort; unordered_set<int> vis; for (auto edge : edges) { int u = edge[0], v = edge[1]; graph[u].push_back(v); // count indegree of each node indeg[v]++; } queue<int> qu; for (auto u : graph) { // add to queue, if indegree // of node u is 0 if (indeg[u.first] == 0) { qu.push(u.first); } } // Run till queue is not empty while (!qu.empty()) { int node = qu.front(); qu.pop(); // add node to topo_sort topo_sort.push_back(node); // traverse adj nodes for (int adj : graph[node]) { // decrement count of indegree // of each adj node by 1 indeg[adj]--; // if count becomes 0, then // add adj to qu if (indeg[adj] == 0) { qu.push(adj); } } } vis.clear(); vector<int> ans; // Take each node from topo_sort for (int node : topo_sort) { // check if node is visited if (vis.count(node) == 0) { vis.insert(node); ans.push_back(node); // Mark all the reachable // nodes as visited dfs(node, vis, graph); } } // finally return ans return ans; }};// Driver codeint main(){ Solution obj; vector<vector<int> > edges = { { 0, 1 }, { 2, 1 }, { 3, 2 }, { 4, 3 } }; // Function call vector<int> ans = obj.solve(edges); for (int n : ans) { cout << n << " "; } cout << endl; return 0;} |
Java
//GFG// JAVA program of the above approachimport java.util.*;public class Solution { // Function to perform DFS private void dfs(int node, Set<Integer> vis, Map<Integer, List<Integer>> graph) { vis.add(node); for (int adj : graph.getOrDefault(node, new ArrayList<>())) { if (!vis.contains(adj)) { dfs(adj, vis, graph); } } } public List<Integer> solve(int[][] edges) { Map<Integer, List<Integer>> graph = new HashMap<>(); Map<Integer, Integer> indeg = new HashMap<>(); List<Integer> topoSort = new ArrayList<>(); Set<Integer> vis = new HashSet<>(); for (int[] edge : edges) { int u = edge[0]; int v = edge[1]; graph.putIfAbsent(u, new ArrayList<>()); graph.get(u).add(v); indeg.put(v, indeg.getOrDefault(v, 0) + 1); } Queue<Integer> qu = new LinkedList<>(); for (int u : graph.keySet()) { if (!indeg.containsKey(u)) { qu.offer(u); } } while (!qu.isEmpty()) { int node = qu.poll(); topoSort.add(node); for (int adj : graph.getOrDefault(node, new ArrayList<>())) { indeg.put(adj, indeg.get(adj) - 1); if (indeg.get(adj) == 0) { qu.offer(adj); } } } vis = new HashSet<>(); List<Integer> ans = new ArrayList<>(); for (int node : topoSort) { if (!vis.contains(node)) { vis.add(node); ans.add(node); dfs(node, vis, graph); } } return ans; } public static void main(String[] args) { Solution obj = new Solution(); int[][] edges = {{0, 1}, {2, 1}, {3, 2}, {4, 3}}; List<Integer> ans = obj.solve(edges); System.out.println(ans); }}// This code is written by Sundaram |
Python3
# Python program of the above approachfrom collections import defaultdict, dequeclass Solution: # Function to perform DFS def dfs(self, node, vis, graph): # add node to visited set vis.add(node) for adj in graph[node]: if (adj not in vis): self.dfs(adj, vis, graph) def solve(self, edges): graph = defaultdict(list) # dictionary storing # indegrees of node indeg = defaultdict(int) # array to store topological # sorting of the array topo_sort = [] vis = set() for (u, v) in edges: graph[u].append(v) # count indegree of each node indeg[v] += 1 qu = deque() for u in graph: # add to ququ ,if indegree # of node u is 0 if(indeg[u] == 0): qu.append(u) # Run till queue is not empty while(qu): node = qu.popleft() # add node to topo_sort topo_sort.append(node) # traverse adj nodes for adj in graph[node]: # decrement count of indegree # of each adj node by 1 indeg[adj] -= 1 # if count becomes 0, then # add adj to qu if (indeg[adj] == 0): qu.append(adj) vis = set() ans = [] # Take each node from topo_sort for node in topo_sort: # check if node is visited if (node not in vis): vis.add(node) ans.append(node) # Mark all the reachable # nodes as visited self.dfs(node, vis, graph) # finally return ans return (ans)obj = Solution()edges = [[0, 1], [2, 1], [3, 2], [4, 3]]ans = obj.solve(edges)print(" ".join(str(n) for n in ans)) |
C#
using System;using System.Collections.Generic;using System.Linq;public class Solution { // Function to perform DFS private void dfs(int node, HashSet<int> vis, Dictionary<int, List<int> > graph) { vis.Add(node); foreach(int adj in graph.GetValueOrDefault( node, new List<int>())) { if (!vis.Contains(adj)) { dfs(adj, vis, graph); } } } public List<int> Solve(int[][] edges) { Dictionary<int, List<int> > graph = new Dictionary<int, List<int> >(); Dictionary<int, int> indeg = new Dictionary<int, int>(); List<int> topoSort = new List<int>(); HashSet<int> vis = new HashSet<int>(); foreach(int[] edge in edges) { int u = edge[0]; int v = edge[1]; if (!graph.ContainsKey(u)) { graph.Add(u, new List<int>()); } graph[u].Add(v); indeg[v] = indeg.GetValueOrDefault(v, 0) + 1; } Queue<int> qu = new Queue<int>(); foreach(int u in graph.Keys) { if (!indeg.ContainsKey(u)) { qu.Enqueue(u); } } while (qu.Count() != 0) { int node = qu.Dequeue(); topoSort.Add(node); foreach(int adj in graph.GetValueOrDefault( node, new List<int>())) { indeg[adj] = indeg[adj] - 1; if (indeg[adj] == 0) { qu.Enqueue(adj); } } } vis = new HashSet<int>(); List<int> ans = new List<int>(); foreach(int node in topoSort) { if (!vis.Contains(node)) { vis.Add(node); ans.Add(node); dfs(node, vis, graph); } } return ans; } public static void Main() { Solution obj = new Solution(); int[][] edges = { new int[] { 0, 1 }, new int[] { 2, 1 }, new int[] { 3, 2 }, new int[] { 4, 3 } }; List<int> ans = obj.Solve(edges); Console.WriteLine(string.Join(", ", ans)); }}// This code is contrubuted by user_dtewbxkn77n |
Javascript
// Function to perform DFSfunction dfs(node, vis, graph) { vis.add(node); for (const adj of graph[node] || []) { if (!vis.has(adj)) { dfs(adj, vis, graph); } }}class Solution { solve(edges) { const graph = {}; const indeg = {}; const topoSort = []; const vis = new Set(); // Build graph and calculate indegree for (const [u, v] of edges) { if (!graph[u]) { graph[u] = []; } graph[u].push(v); indeg[v] = (indeg[v] || 0) + 1; } // Enqueue all nodes with 0 indegree const qu = []; for (const u of Object.keys(graph)) { if (!indeg[u]) { qu.push(u); } } // Perform topological sort while (qu.length) { const node = qu.shift(); topoSort.push(node); for (const adj of graph[node] || []) { indeg[adj]--; if (indeg[adj] === 0) { qu.push(adj); } } } // Perform DFS on unvisited nodes in topoSort vis.clear(); const ans = []; for (const node of topoSort) { if (!vis.has(node)) { vis.add(node); ans.push(node); dfs(node, vis, graph); } } return ans; }}// Driver codeconst obj = new Solution();const edges = [ [0, 1], [2, 1], [3, 2], [4, 3],];// Function callconst ans = obj.solve(edges);console.log(ans.join(" "));// This code is contributed by phasing17 |
Output
0 4
Time Complexity: O(N)
Auxiliary Space: O(N)
Approach 2: The given problem can also be solved using the observation that vertices with in-degree 0 are the vertices that can not be reached from any other vertex. Hence, the idea is to find the indegree of each vertex and insert the vertices with in-degree 0 into the required set, as all the other vertices can be visited eventually.
Below is the implementation of the above approach:
C++
// C++ program of the above approach#include <bits/stdc++.h>using namespace std;// Function to find smallest set// of vertices from which the// complete graph can be visitedvector<int> solve(vector<vector<int>>& edges){ map<int, int> graph; // Dictionary storing // indegree of nodes map<int, int> indeg; for(auto dt : edges) { graph[dt[0]] = dt[1]; // Count indegree of // each node indeg[dt[1]] += 1; } vector<int> ans; for(auto it = graph.begin(); it != graph.end(); ++it) { // Add to ans, if indegree // of node u is 0 if (!indeg.count(it->first)) ans.push_back(it->first); } // Return Ans return ans;}// Driver codeint main(){ vector<vector<int>> edges = { { 0, 1 }, { 2, 1 }, { 3, 2 }, { 4, 3 } }; vector<int> ans = solve(edges); for(auto dt : ans) cout << dt << " "; return 0;}// This code is contributed by rakeshsahni |
Java
// Java program of the above approachimport java.util.*;class GFG{// Function to find smallest set// of vertices from which the// complete graph can be visitedstatic Vector<Integer> solve(int[][] edges){ HashMap<Integer,Integer> graph = new HashMap<Integer,Integer>(); // Dictionary storing // indegree of nodes HashMap<Integer,Integer> indeg = new HashMap<Integer,Integer>(); for(int dt[] : edges) { graph.put(dt[0], dt[1]); // Count indegree of // each node if(indeg.containsKey(dt[1])) { indeg.put(dt[1], indeg.get(dt[1])+1); } else indeg.put(dt[1], 1); } Vector<Integer> ans = new Vector<Integer>(); for (Map.Entry<Integer,Integer> it : graph.entrySet()) { // Add to ans, if indegree // of node u is 0 if (!indeg.containsKey(it.getKey())) ans.add(it.getKey()); } // Return Ans return ans;}// Driver codepublic static void main(String[] args){ int[][]edges = { { 0, 1 }, { 2, 1 }, { 3, 2 }, { 4, 3 } }; Vector<Integer> ans = solve(edges); for(int dt : ans) System.out.print(dt+ " ");}}// This code is contributed by shikhasingrajput |
Python3
# Python program of the above approachfrom collections import defaultdictclass Solution: # Function to find smallest set # of vertices from which the # complete graph can be visited def solve(self , edges): graph = defaultdict(list) # dictionary storing # indegree of nodes indeg = defaultdict(int) for (u,v) in edges: graph[u].append(v) # count indegree of # each node indeg[v] +=1 ans = [] for u in graph: # add to ans, if indegree # of node u is 0 if(indeg[u] == 0): ans.append(u) # Return Ans return (ans) obj = Solution()edges = [[0,1] , [2,1] , [3,2] , [4,3] ]ans= obj.solve(edges)print(" ".join(str(n) for n in ans)) |
C#
// C# program of the above approachusing System;using System.Collections.Generic;public class GFG { // Function to find smallest set // of vertices from which the // complete graph can be visited static List<int> solve(int[, ] edges) { Dictionary<int, int> graph = new Dictionary<int, int>(); // Dictionary storing // indegree of nodes Dictionary<int, int> indeg = new Dictionary<int, int>(); for (int k = 0; k < edges.GetLength(0); k++) { int keys = edges[k, 0]; int values = edges[k, 1]; graph.Add(keys, values); // Count indegree of // each node if (indeg.ContainsKey(values)) { indeg[values] += 1; } else indeg.Add(values, 1); } List<int> ans = new List<int>(); foreach(KeyValuePair<int, int> it in graph) { // Add to ans, if indegree // of node u is 0 if (!indeg.ContainsKey(it.Key)) ans.Add(it.Key); } // Return Ans return ans; } public static int[] GetRow(int[, ] matrix, int row) { var rowLength = matrix.GetLength(1); var rowVector = new int[rowLength]; for (var i = 0; i < rowLength; i++) rowVector[i] = matrix[row, i]; return rowVector; } // Driver code public static void Main(String[] args) { int[, ] edges = { { 0, 1 }, { 2, 1 }, { 3, 2 }, { 4, 3 } }; List<int> ans = solve(edges); foreach(int dt in ans) Console.Write(dt + " "); }}// This code is contributed by 29AjayKumar |
Javascript
// Javascript program of the above approach// Function to find smallest set// of vertices from which the// complete graph can be visitedfunction solve(edges) { let graph = new Map(); // Dictionary storing // indegree of nodes let indeg = new Map(); for (dt of edges) { graph.set(dt[0], dt[1]); // Count indegree of // each node if (indeg.has(dt[1])) { indeg.set(dt[1], indeg.get(dt[1]) + 1); } else indeg.set(dt[1], 1); } let ans = new Array(); for (key of graph.keys()) { // Add to ans, if indegree // of node u is 0 if (!indeg.has(key)) ans.push(key); } // Return Ans return ans;}// Driver codelet edges = [[0, 1], [2, 1],[3, 2], [4, 3]];let ans = solve(edges);for (dt of ans) console.log(dt + " ");// This code is contributed by Saurabh Jaiswal |
Output
0 4
Time Complexity: O(N)
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!
