code_astra's blog

TopCoder SRM 691
By code_astra, history, 8 years ago, In English

Can anyone post a detailed solution to Div 2 500 pointer of SRM 691 ?

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

Comments Comments (13)
| Write comment?
»
8 years ago, # |
  Vote: I like it +19 Vote: I do not like it

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.

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

    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 ?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 3   Vote: I like it +14 Vote: I do not like it

      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.

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

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

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

    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 ?

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

      (2x - 1) - (2y - 1) = 2x - 2y, where x = Number of nodes in the component and y = Number of nodes in the tail(s).

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

div 2 1000 anyone ?

→ Reply