### PROBLEM LINK:

**Author:** Jay Pandya

**Tester:** Hiroto Sekido

**Editorialist:** Anton Lunyov

### DIFFICULTY:

EASY

### PREREQUISITES:

### PROBLEM:

Getting rid of the story line the problem simply asks to find the number of articulation points in the undirected graph and multiply it by **K**.

### EXPLANATION:

Naive approach would be for each vertex delete it from the graph and check the connectivity. Such approach has complexity **O(N * M)** and should get TLE. So something clever should be invented.

The problem could be solved using simple DFS in **O(N + M)** time. For this, some magic value **low(v)** is calculated for each vertex **v** and this allows to check whether **v** is articulation point in **O(1)** time inside DFS. The root of the DFS traversal tree should be analyzed in another way. Namely it will be an articulation point if and only if it has at least two sons in this tree.

But sincerely speaking biconnected components, articulation points and bridges is one of my unfavorite topics

So I prefer to forward you to some existing tutorials for further details of the mentioned approach:

- Exercise 23-2 in famous book “Introduction to Algorithms” by Cormen and others.
- The article on e-maxx.ru. It seems to be very well written but unfortunately it is only in Russian. But code there is working - I’ve checked and get AC here But be careful with
`IS_CUTPOINT(v);`

it could say this several times for the same vertex. - The article at Wikipedia. Unfortunately it contains no code snippets so it could be hard to learn this topic efficiently from there.
- Yet another tutorial. It seems to be really good introduction to DFS and its applications with code snippets.
- Several other tutorials: click, click, click.

Also I provide a lot of related problems on biconnected components, so don’t blame me much for not writing yet another tutorial on this topic

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution will be provided soon.

Tester’s solution can be found here.

### RELATED PROBLEMS:

UVA - 796 - Critical Links

TJU - 2840 - Apple Tree

UVA - 610 - Street Directions

UVA - 10972 - RevolC FaeLoN

PKU - 3177 - Redundant Paths

Live Archive - 4186 - Lucky cities