How to solve Single Point of Failure (Failure) from November Long 2019

Red is way beyond me unless I get a heck of a lot smarter :slight_smile:

Many thanks for the kind words! :smiley:

2 Likes

Very elegant, so cool. This is should be the official editorial.

2 Likes

@ritik_gajjar ye kaise pata karenge ki ek node kitne cycles me contribute kr rha h?

@ritik_gajjar let’s take this graph:
1 -> 2
2 -> 3
3 -> 4
4 -> 5
5 -> 1
According to you every node is contributing in two cycles? Or am i missing something?

Got it. By the way my intension was to ask if there is a way to find for a node in exactly how many cycles it belongs to.
I solved this problem by removing bridges.

most of people solved by removing bridges.

My idea is - find a cycle (any if found - O(E) ) our SPF must be in this cycle (if present) remove the edges involved in this cycle and for every vertex in this cycle run DFS by a common visited check-up array .
This may lead to ( for each vertex in cycle)
1. a rooted tree with this vertex as root
2. may end-up visiting some vertex(s) in this cycle
3. may lead to a a sub-graph with cycle
(-guess the checks in these cases)
this total time - O(E) :stuck_out_tongue: (not implemented)

Is this weak test cases or correct solution.
For β€œFailure”.
What I did was find all biconnected components. And use DSU to check if two edges are in same biconnected component or not.
Then for each node we need to find the number of connected components the graph will have if we remove current node.
For finding that we find number of different biconnected components beside current node.
Then it’s just logical check ( each tree will have n-1 edges property)
This will be Delta of initial connected component for each node.