Блог пользователя YouKn0wWho

Автор YouKn0wWho, 6 лет назад, По-английски

I am stuck on this following problem:

Statement:

Given an undirected connected simple graph of n nodes and m edges, for each node i from 1 to n you need to find if this node was not present in this graph how many connected components the graph would have.

Constraints:

1<=n,m<=100000

Example:

Input:

4 4 //4 nodes and 4 edges

1 2

2 3

2 4

3 4

Output:

1 2 1 1

Note:

A node is not present means erasing the node and its edges

Trivia:

Thanks for reading the problem. It will be really helpful if you can give me a solution.

  • Проголосовать: нравится
  • +15
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

It seems like you want to find the biconnected components in the graph. The answer for some vertex is then the amount of such components it is in.