Hi.
There is a problem but I didn't find it in codeforces. If you can help me to find it and solve it.
There is n
cities and m
road between them. roads are two-way. Capital is city z
. We define city x
critical for city y
if all the ways for going from z
to y
, contain x
. If we want to find that x
is critical for y
or not, an easy way is to use dfs to find that is there any way from capital to y
or not. then do another dfs but x
removed from graph (avoid dfs from going to x
). based on this two dfs, we can understand that x is critical or not for y
.
However in this new problem we want to find number of critical cities. (all x
and y
). However I don't remember that there is a capital or not. if there is no capital, then we must try all z
too. If we do last idea, there is a time limit. I want a better way.
I didn't found problem in codeforces but I know that exists in codeforces, I just don't save it!
Is it possible to help me?
I'm sorry for bad English. Thanks.
This is a standard problem called
finding articulation points
. You can learn about it here: https://cp-algorithms.com/graph/cutpoints.html