2876. Count Visited Nodes in a Directed Graph | Weekly Leetcode 365

[@nabajyotimajumdar4511]

Great explanation!

[@MayankGour-c9p]

Great observation :), one follow up what if there can be multiple outgoing edges for a node ? then i guess we have to use strongly connected component and then condensed the graph after finding the component and do the required processing...

[@VishalYadav-gk1kg]

Very nice explanation sir, Thank you!

[@kshitij_kaithal]

Thanks for the wonderful explanation and intuition building😄 Keep up the good work for the community.

[@vinayakbhat8495]

Really good explanation. Thanks!

[@loserfruit9663]

Awesome

[@chaitanya812]

Kafi sahi smjhaya bro

[@AshutoshChoudhary2004]

Please bring more videos of Segment Tree series

[@sarathtchander]

Getting TLE public static int[] countVisitedNodes(List edges) { int n = edges.size(); int[] result = new int[n]; List adjList = new ArrayList(); for (int i = 0; i < n; i++) { adjList.add(new ArrayList()); } for (int i = 0; i < n; i++) { adjList.get(i).add(edges.get(i)); } for (int i = 0; i < n; i++) { boolean[] visited = new boolean[n]; result[i] = bfs(adjList, i, visited); } return result; } static int bfs(List adjList, int src, boolean[] visited) { int ans = 0; Queue q = new ArrayDeque(); q.add(src); while (!q.isEmpty()) { ans++; int curr = q.poll(); if (visited[curr]) break; visited[curr] = true; for (int nbr : adjList.get(curr)) { if (visited[nbr]) break; q.offer(nbr); } } return ans; }

[@nikhilkumarv2577]

sike editorial 🔥

[@chiragahuja4727]

thanks. but what if the graph is not-connected. for example : [6,3,6,1,0,8,0,6,6] this graph. In this graph 1->3->1 is a cycle and 0->6->0 is also a cycle. how to solve this issue? this is my code. ``` class Solution { HashMap adj; public int[] countVisitedNodes(List edges) { // O(n) - Approch // note -> there must exist only one cycle in the graph (why? bcz it's connected and each node has only 1 outgoing edge) -- that cycle will for sure exist bcz that last node will have to go to somewhere. // detect length of the cycle -> ans[u] = length of the cycle (for each node in the cycle) // use dp to fill values other node of the graph -- dfs // find nodes present in the cycle -- using bfs // 0 -> 1 -> 2 -> 3 -> 1 (graph) // queue {0} -> {0, 1} -> {0, 1, 2} -> {0, 1, 2, 3} -> reaches 1 again // remove values from queue until you get 1 // {3, 2, 1} => list of nodes in the cycle int n = edges.size(); int[] res = new int[n]; Arrays.fill(res, -1); Stack q = new Stack(); boolean[] vis = new boolean[n]; q.push(0); int removeTill = -1; while(!q.isEmpty()){ int u = q.peek(); vis[u] = true; int v = edges.get(u); if(vis[v]){ removeTill = v; break; } q.push(v); } List cyclicNodes = new ArrayList(); while(!q.isEmpty() && q.peek() != removeTill) cyclicNodes.add(q.pop()); cyclicNodes.add(removeTill); System.out.println(cyclicNodes); for(int u : cyclicNodes) res[u] = cyclicNodes.size(); // fill other nodes values which were not in the cycle -- dfs // for(int u=0; u

[@codingmohan]

Why is this an issue? The same logic would work here. It’s just that your DFS would find 2 different cycles. Let me know where you are facing issue / why you think it might cause issues and I may be able to help better

[@dhairyachauhan6622]

bhaiya if possible do live code it would help in understanding. I saw your profile and you reached guardian :p. How do i do it.... :(

[@user-le6ts6ci7h]

At 7:52 you have made a wrong assumption , that you considered two edges from a node , which is not possible, there can't be 2 edges from a node thus one cycle in the entire graph

[@codingmohan]

I was trying to explain that there can be 2 type of scenarios possible - 1st which we have seen already and second which is shown there after,

[@trishulcurtis1810]

There can more than one cycle in this graph

[@SurajYadav-py1do]

why it is not work for bfs even only 932/941 test cases is passed for rest of 9 test case it gives time limit exceed why bro ........??

[@codingmohan]

If you can share your approach, I may be able to help better.

[@lingasodanapalli615]

This is my code: Getting this TLE error: 941 / 941 test cases passed, but took too long. Can someone please help? class Solution { public: vector result; vector mainVisited; vector adjMatrix; void BFS(int source, vector &currentNodes){ queue q1; q1.push(source); while(!q1.empty()){ int current = q1.front(); mainVisited[current]=1; currentNodes.push_back(current); q1.pop(); for(auto child: adjMatrix[current]){ if(!mainVisited[child]){ q1.push(child); mainVisited[child]=1; } } } } vector countVisitedNodes(vector& edges) { int n = edges.size(); result.resize(n, n); mainVisited.resize(n, 0); adjMatrix.resize(n); vector hashMap(n, 0); for(int i=0; i

[@tejaskatkade6785]

i have gone through same...dont make any adjcency list and it will pass all the testcases.