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

Center of a tree
Автор vkditya0997, история, 8 лет назад, По-английски

Hello everyone,
I have seen many problems which can be solved using tree center.
So, I would like to know about it.
If someone can provide resources or explain it here in comments, It would be great!

and also my approach for today atCoder Problem C was something like this : ( failed! )

  • Find an extreme of a diamemter of tree, This can be done by running a dfs from any arbitrary node. The node whose depth is highest is one of the extreme. ( Please correct me? )
  • find the diameter from this extreme ( the highest depth from this node ).
  • the nodes with the depth equal to the diameter are pushed into a vector ( let's say A ).
  • Now, for every node in the vector A, Run a dfs and count the no of nodes having depth greater than K. the minimum of these would be the answer.


Where did I go wrong?
Someone please help me?

Thanks in Advance

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

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

Consider a graph

0 1
1 2
3 2
3 4
5 4
6 5
7 6
8 7
10 9
11 9
12 9
13 9
14 9
14 4

with K = 2. Now, the extreme diameter is 8 (between 0 and 8), but the optimal solution is to pick vertices 9-14, none of which even lies on the longest path.

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

There is a very nice and easy to implement algorithm for finding center of a tree.

1) Push all the leaves in a queue.
2) Remove the top element and remove the edges , if new leaves form push in queue.
3) The last node to be pushed in the queue is the Center

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

    Doesn't work for all graphs, only for trees.

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

      Yeah by mistake I wrote graph.

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

        What all things can be done by finding the center of a tree? Can you give one or two applications?

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

          Popular example might be Problem ( I am not sure though as I haven't solved it but I have heard it can be solved by finding absolute center ) .

          Other problems generally ask directly for center after updates. I haven't really seen much problems on center.

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

    From what I've understood this will find a center, not necessarily all centers (i.e, if there exists a second). Can this algorithm be applied in a way that finds all centers?

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

In your second dfs, where you find the diameter using the extremal vertex, you should store the parents for every node. Then you can do this simple code to find the center after your dfs is finished:

current = vertex_with_maximum_distance
while dist[current] > diameter/2:
    current = parent[current]
center = current
→ Ответить
  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Hi! Late but I've tried to retrace the path from the end of the diameter to the point where the distance is half of the diameter. But this doesn't seem to work correctly. Can anyone please help me out with this?

            // Method1: WA for some reason
        int reqDepth = depth[diaEnd2] / 2;
        int temp = diaEnd2;
        while (temp != diaEnd1)
        {
            if (depth[temp] == reqDepth)
            {
                cout << temp << endl; // center found
                return;
            }
            temp = parent[temp];
        }

        // Method2: AC
        int temp = diaEnd2;
        while (depth[temp] > depth[diaEnd2] / 2)
        {
            temp = parent[temp];
        }
        cout << temp << endl; // center found
    → Ответить