FAILURE : NOV 2019 Long challenge video editorial

Here is the link to the video editorial.
FAILURE

solution code link : FAILURE(ideone)

if you find this helpful , let me know in the comment here.
if you want to donate you are always welcome , that would help the channel to grow.

Other PlayLists from my channel

  1. Other codechef editorials(17 Videos currently(
  2. Disjoint Data set Course (7 Videos currently)
  3. Segment Tree Course : (3 Videos Currently)
  4. Basics of DP(4 Videos Currently)

If you guys have any contribution or any suggestions for this channel , let me know.
Thank you.

13 Likes

Nice video bro.

Its quite simple.

Step 1: Does the graph have a cycle? If not print -1.
Step 2: Remove all bridges. Then each and every edge will be part of a cycle.
Step 3: Find out the vertex with most .edges. If there are multiple choose the smallest such vertex
Step 4: Delete the vertex and remove all its edges.
Step 5: Does graph still have a cycle? If so, print -1. If not, print vertex number.

1 Like

well thank you .

Waqar, didn’t yet watch the video since I am work. But thanks for sharing. WIll watch from home.

Nice video bro. Keep it up, and when you get time do make video editorials for other problems too.

i have a simple idea, i wish it will be useful :
you can use properties of cycle in graph (the difference between tree and graph)
if the number of edges in a connected components is more than the number of vertex - 1 --> we have cycle in this connected :
step 1 : if we have found an answer before : print -1 and break everything
step 2 : sort the vertexes which belong to last connected (store it when you visited it) and try to apply DFS on it from smaller one but make sure, you have to pass it and don’t visit it, and you can pass some of them by try to delete its edges and compare (this condition will make deference for saving time)
count the number of edges in the new connected (maybe will appear more than one) and compare it , if you don’t have a cycle then the answer will be the last vertex you tried to delete it
if you don’t find the suitable vertex then print -1 and break everything
step 3 : continue the searching for more connected components, if you finish without a break then print the answer (don’t forget you have to make the answer = -1 before you start the searching)

I don’t think you need to watch the video.

Only to see how you are doing!

Awesome bruh. We have to check for all nodes in highest order degree array?

testing only 1 node with highest degree is enough

I found this one interesting too.

1 Like

when I get time , sure i will.

but bro i m not getting how to remove edges who are in cycle should i do Tarjan algo i m not able to get that

first use set to store adjacency list so we can remove edges in logn time.
then find bridge edges (using this algorithm )https://cp-algorithms.com/graph/bridge-searching.html

then you can simply remove them from set.