Leetcode 2360. Longest Cycle in a Graph | Weekly Contest 304. Hard Problem 4

Просмотров 10 тыс.

% 283

Use coupon ALISHA on any GeeksforGeeks course to get 10% discount:
practice.geeksforgeeks.org/courses
Connect with me on LinkedIn : www.linkedin.com/in/alisha-parveen-80579850/
Check out our other playlists:
Dynamic Programming:
ru-vid.com/group/PLLT4EuYB4kIY_DWiiFY_TW3Egm9pmZPuS
Trees:
ru-vid.com/group/PLLT4EuYB4kIZzjDUX5VKsU9ECdIlsOdkd
Heaps and Maps:
ru-vid.com/group/PLLT4EuYB4kIatB7uwwkTDq9m-KQkD_out
Arrays and Maths:
ru-vid.com/group/PLLT4EuYB4kIb0G4k2LxdIs2dCaj9vebqC
Bit Manipulation:
ru-vid.com/group/PLLT4EuYB4kIZGBE71Udl0m68uFxRiMhGS
Greedy Algorithms:
ru-vid.com/group/PLLT4EuYB4kIZaOVWhgBnQr9w5JxgHAEld
Sorting and Searching:
ru-vid.com/group/PLLT4EuYB4kIaWgO_-unJeY4huZlP3Uln9
Strings:
ru-vid.com/group/PLLT4EuYB4kIah6F-m0v-zfrQKg1G1zAJC
Linked Lists:
ru-vid.com/group/PLLT4EuYB4kIZp5ApjgO_5K69Jv4GAGUYt
Stack and Queues:
ru-vid.com/group/PLLT4EuYB4kIY2nfXL0sxzHbDHReuMw_sE
Two Pointers:
ru-vid.com/group/PLLT4EuYB4kIbclnecGeKq8vmMdaFYdNyu
Graphs, BFS, DFS:
ru-vid.com/group/PLLT4EuYB4kIb5er32BqvSqnFFxJ0Ciqf7
Backtracking:
ru-vid.com/group/PLLT4EuYB4kIZfNt7M9FMfcJEiE5E8pmFL
Non- DSA playlists:
Probability:
ru-vid.com/group/PLLT4EuYB4kIZWrGlLjATLbuX7CRitUrq6
SQL-Basic Join functions:
ru-vid.com/group/PLLT4EuYB4kIZZxUKWLLufuviTI4jWhSHN
SQL-Basic Aggregate functions:
ru-vid.com/group/PLLT4EuYB4kIa5OBKfvrPRZB6tSVcxhVJN

Опубликовано:

31 июл 2022

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 38

@probabilitycodingisfunis1 2 года назад

int longestCycle(vector& edges) { vectordist_node(edges.size(),0); vectorextra(edges.size(), false); vectorvisited(edges.size(),false); int ans = -1; for(int i=0;i

@saunaknandi1814 Год назад

Alisha instead of taking extra array, what we can do is we will take new distances array in base loop.

@arpitkhanulia7 Год назад

That was a Great Explanation. a similar variant was asked in today's POTD in gfg void dfs(vector&adj,vector&vi,vector&extra,vector&distance,int &ans,int& node,int d){ if(node != -1) { if(!vi[node]) { vi[node] = 1; extra[node] = 1; distance[node] = d; dfs(adj,vi,extra,distance,ans,adj[node],d+node); } else if(extra[node]) ans = max(ans, d - distance[node]); extra[node] =0; } } long long largestSumCycle(int N, vector Edge) { // code here int ans=-1; vectorvi(N); vectorextra(N); vectordistance(N); for(int i=0; i

@anchalkumari5832 Год назад

Great Explanation, Thank you Ma'am !!!

@arghyadas2836 Год назад

Will the code change if there were more than one outgoing edges? Why is it important to have atmost one outgoing edge?

@sgcreations5638 Год назад

Amazing Explanation you made this question easy 👏.

@MP-ny3ep Год назад

Phenomenal explanation as always ! Thank you , very comprehensible.

@jeevanaadhaar-mereprabhu Год назад

Very nice explaination as always Alisha, can you please tell me how many years you practiced to get intuition of this level ?

@shikhasoni9992 Год назад

You explain very well i really love it❤

@vaibhavgupta973 Год назад

thank you Alisha !!

@soumyajitganguly2593 2 года назад

If you keep integers in the visited array which is a global counter for dfs steps taken, you dont need the extra array.

@shivanshgupta1509 2 года назад

Thankyou mam!!!! And new Thumbnail is great!!!!!!

@akshhay Год назад

Is this similar to tarjans SCC algorithm?

@kunalrautela3562 2 года назад

Amazing Explanation .Please if you could make a video on Leetcode 834 Sum of Distance in Tree

@pushkarraj4640 2 года назад

Instead of creating extra vector can we clear visited vector before making the new dfs call ?

@hari-codes 2 года назад

Same doubt

@soumyajitganguly2593 2 года назад

@@hari-codes yea you can, but you will get TLE. Think about a cycle will 10K nodes and every time you encounter this cycle you will traverse the full 10K nodes.

@themarketverse 2 года назад

Great work Alisha..Your explanations are so easy to understand ✨✨

@silupanda7066 2 года назад

Clear and concise explanation Alisha!

@rishav144 2 года назад

thanks ....keep posting contest solutions .....Its very helpful

@ThejaswiKumarGP 2 года назад

Damm, this is called the explanation and vision

@champion5946 Год назад

Great Explaination Mam/Didi

@BHARATKUMAR-jl1jp 2 года назад

Amazing Explanation as always🤩🤩

@aasthagoyal5059 2 года назад

Can anyone tell me what's the indian timing of leetcode contest?

@akashjha822 2 года назад

Saturday 8 PM Sunday 8 AM

@Panichusko 8 месяцев назад

it's giving mle how to optimize it further

@siddharthsingh8472 2 года назад

thank you helped alot

@barathnatarajan8566 2 года назад

wonderful explanation

@gunahawk6893 2 года назад

Missing old hostel background

@zishan53 2 года назад

Nice explanation

@AmarjeetKumar-to9ub Год назад

🔥++

@abhay-zw3yw 2 года назад

Smooth...

@piyush9409 Год назад

I have a better solution with only one visited vector :) void dfs(int node,vector &vis,vector &edges,vector &dist,int dis,int &ans){ if(node!=-1){ if(vis[node]==0){ vis[node]=2; dist[node]=dis; dfs(edges[node],vis,edges,dist,dis+1,ans); } else if(vis[node]==2){ ans=max(ans,dis-dist[node]); } vis[node]=1; } } int longestCycle(vector& edges) { int n=edges.size(); vector vis(n,0); vector dist(n,0); int ans=-1; for(int i=0;i