| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
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
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.
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.
I have just got accepted, your idea is correct. When running dfs to create dfs-tree, we can maintain the size of current component.
Good to hear that. Good job !
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. :)
Is it a problem from any online judge? If so, can you give the link to the problem?
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.
So this was today's F!!!
It was so damn lengthy just to implement. Hundreds of things just to get an AC.
I would disagree. I recommend reading this blog: https://codeforces.net/blog/entry/68138. Then the implementation becomes very easy, you just store subtree sizes for each node in the DFS tree and perform the bridge-finding algorithm as usual. Here is my code: https://codeforces.net/contest/1986/submission/267026227.
Yea, I also thought about that algo but forgot its logic so I just left it for upsolving.