Can anyone post a detailed solution to Div 2 500 pointer of SRM 691 ?
Can anyone post a detailed solution to Div 2 500 pointer of SRM 691 ?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3810 |
| 2 | Benq | 3676 |
| 3 | Kevin114514 | 3655 |
| 4 | maroonrk | 3463 |
| 5 | strapple | 3447 |
| 6 | Um_nik | 3387 |
| 7 | heuristica | 3322 |
| 8 | turmax | 3317 |
| 9 | tourist | 3307 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 156 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | Um_nik | 141 |
| 5 | Errichto | 139 |
| 6 | adamant | 137 |
| 7 | AmShZ | 135 |
| 8 | BledDest | 132 |
| 9 | maroonrk | 131 |
| 10 | qwexd | 129 |
First, build a directed graph with edge i -> a[i]. The graph should contain many components and the component are either cycle or cycle with a tail
Think of the graph has many components. Now the answer should be the multiply of number of ways so each node for the component can have a path to vertex n.
If the component is just a cycle. The number of valid way will be 2^(number of nodes in component)-1. As no matter which vertex is selected , there will still be a path for each vertex. But have to choose at least one as there are many components and need to use vertex n as a bridge to connect.
If the component has a tail, the ways are (2^(number of node in the cycle)-1) * 2^(number of node in tail). As if no node in the cycle connect to vertex n. The nodes in the cycle cannot reach vertex n.
At last, if the original graph only has one component. Answer should +1 as all node can no connect vertex n and still remain connected.
Thank you so much! But how to find out number of vertices in a cycle in a component in a graph? Is there a standard algorithm for it ? If so please provide a link . Also in the question nowhere it is explicitly mentioned as a directed graph , so how is it you took it to be one ?
As this time the number of vertex is small. Simple dfs can find the cycle. Mentioned by animeshf.
For larger n, There are some O(N + M) algorithm.
For undirected graph finding cycle(biconnected component), tarjan algorithm can be used click me
For directed graph finding cycle(strongly connected component), Kosaraju's Algorithm(tarjan algorithm also) can be usedclick me
Also, the graph is actually undirected. But i think it is easier to think of the graph that which edge will point at vertex n after node u is chosen as there is only one outgoing edge for each node. So after all, you still have to consider it as undirected.
For functional graph, you can also use Floyd's cycle-finding algorithm
Thanks a lot.
Actually, simple dfs can find the cycle in O(N) for directed graphs with N nodes and N edges, with each node having outdegree 1 (as in the SRM question).
Thanks a lot !! Passed
I built an undirected graph and found all bridges in it.
If edge (u, v) is a bridge and a[u] = v, then u is a bad node. So just compute the size of each component and number of bad nodes in each component and then use the formulae as mentioned by Bedge.
So connectivity was undirected in the question, hence I didn't even bother thinking of the problem in terms of a directed graph. You can implement what Bedge said by doing a simple dfs on the transpose graph. Doing a dfs on the transpose graph will maintain the cycle (the direction of the edges in the cycle will be reversed), and enable you to visit the nodes in the tail(s) as well. So whenever you encounter the edge (x, y) that forms the cycle, you can conclude that number of nodes in the cycle is depth[x] + 1
So in the case of a component with tails the total number of bad nodes is equal to the number of nodes in tails ? so the number of ways would be : 2^(ncycle-1)*2^( nbad ) yes ?
(2x - 1) - (2y - 1) = 2x - 2y, where x = Number of nodes in the component and y = Number of nodes in the tail(s).
OK just one last doubt is your bad nodes equivalent to tail nodes ?
Yes
div 2 1000 anyone ?