YouKn0wWho's blog

By YouKn0wWho, 4 months ago, In English,

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.

 
 
 
 
  • Vote: I like it  
  • +15
  • Vote: I do not like it  

»
4 months ago, # |
  Vote: I like it +22 Vote: I do not like it

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.

»
4 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Nvm. I found a counterexample.