minimum number of vertices to reach all nodes leetcode | leetcode 1557 | graph

#Graph #InDegree #DAG #Coding #Programming #Interview #Practice #Leetcode #Problem1557 #Minimum_Number_of_Vertices_to_Reach_All_Nodes #Algorithm #Java #Preparation #NG #nickode

[NareshGupta]

Note: We don't need to build the Graph, we can just solve it with inDegree array by iterating all the edges.

Complexity Analysis: Time - O(E), Space - O(V)

[imranwahid]

But what is the intuition of the algorithm?

[gauravkumar]

this is the best solution

int degree[]=new int[n];
List<Integer> res=new ArrayList<Integer>();
for(List<Integer> x: adj){
indegree[x.get(1)]++;
}

for(int i=0; i<n;i++){
if(indegree[i]==0){
res.add(i);
}
}
return res;

[coder]

con you please tell what does the fact " unique path is guaranteed" helps in coming to the solution

[Werewolf]

But what is the purpose of creating the graph, I mean without creating the graph, only using the ndegree array we can get this. Please explain?