EternalFire's blog

Bridge in graph
By EternalFire, history, 5 years ago, In English

Given a connected unweighted undirected graph with N (N <= 100000) vertices and M (M <= 200000) edges (there is no multiedge nor loop). For each bridge in graph determine the size of two subgraphs formed by removing this bridge.

I am trying to solve a problem, but I have just encountered this subproblem when following my approach. Could anyone have an idea to solve above problem? Thanks

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

Comments Comments (7)
| Write comment?
»
5 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

I would try this approach: Root at some vertex, and calculate size of each subtree, then you can for each edge (u,v) calculate that one subgraph has d[root]-d[v], and other one have size_of_subtree-(d[root]-d[v]). Where d[x] size of subtree with vertex x as root.

→ Reply
»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I am not sure for my idea, but I will just say what I am thinking and maybe it can help. I will call sub-graphs that are 2-connected as "blocks". So now you can imagine the graph as a tree of blocks, where the nodes of the tree is a bunch of nodes that form a sub-graph which does not have bridge and the edges of the tree are the bridges of the initial graph. With that idea, now maybe you can pre calculate the sizes of subtrees and get the answer you need.

If you think about it and you find it a good idea, I can continue with the specific algorithm I have in my mind.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    I have just got accepted, your idea is correct. When running dfs to create dfs-tree, we can maintain the size of current component.

    → Reply
»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Direct application of Bridge Tree.
If you shrink each component in a node and keep the bridges as edge, then the graph will turn into a tree. Then you can assign component size as weights to node, and solve it for a tree.
There are other applications of this tree, check them out. :)

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it a problem from any online judge? If so, can you give the link to the problem?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    It's on SPOJ. Unfortunately, I couldn't find any statements of problem in English. But I think I can describe it here:

    Given an undirected graph (doesn't have to be connected) with N vertices (N <= 100000) and M edges (M <= 200000), containing no loop nor multiedge. One operation is following: First, delete an edge of the graph. Then you must add an edge connecting two different vertices which has never been existed before. You should count the number of ways to perform single operation, such that the result graph is connected. Two operations are different with each other if one of the following conditions hold:

    • The edges deleted by two operations are different.

    • The edges added by two operations are different.

    → Reply