Borjianamin's blog

By Borjianamin, history, 4 weeks ago, In English,

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.

 
 
 
 

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

This is a standard problem called finding articulation points. You can learn about it here: https://cp-algorithms.com/graph/cutpoints.html