TheCreator's blog

What is the most optimal solution for this problem ?
By TheCreator, history, 3 weeks ago, In English

Given a connected undirected graph consisting of N N nodes, determine how many connected components the graph will break into if each node is removed.

For example, consider a graph with the following undirected edges:

1-2, 1-3, 1-4, 4-5, 5-6, 4-6.

If we remove node 1, there will be 3 connected components. If we remove node 2, there will be 1 connected component. If we remove node 3, there will be 1 connected component. If we remove node 4, there will be 2 connected components. If we remove node 5, there will be 1 connected component. If we remove node 6, there will be 1 connected component.

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

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

Auto comment: topic has been updated by TheCreator (previous revision, new revision, compare).

→ Reply
»
3 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I am wrong, disregard :)

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually, you need to count the number of articulation points, not the number of bridges, you can see why by this example:

    1 2

    1 3

    3 2

    2 4

    2 5

    4 5

    here, there isn't any bridge but by removing node 2, there gonna be two connected components

    → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I don't know how to quickly calculate the number of connected components by removing each articulation point, still thinking about it

      → Reply
»
3 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

https://github.com/wery0/CP-library/blob/master/Graphs/Graph/Graph.cpp#L95

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    bro has every single graph problems as a callable function in his library, holy shit

    → Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

This problem appeared in a recent Atcoder Beginner Contest, ABC334G: Christmas Color Grid 2 and ExplodingFreeze showed me an elegant way to compute this value.

→ Reply