Блог пользователя code_astra

TopCoder SRM 691
Автор code_astra, история, 8 лет назад, По-английски

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

  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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 ?

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится +14 Проголосовать: не нравится

      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.

      → Ответить
»
8 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 ?

    → Ответить
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

div 2 1000 anyone ?

→ Ответить