Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

Le_Savage's blog

By Le_Savage, 4 weeks 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 weeks 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 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Nvm. I found a counterexample.