Given the number of vertices (N). Next comes the description of the N-1 edge in the graph, that is, the beginning and end of the edge. There is only one path between any two vertices. The graph itself is undirected.

Purpose: to find such a vertex in the graph, by removing which, the graph would split into at least two new smaller graphs, the number of which vertices are the same. If there is no such vertex, print -1.

I did something like this: for each vertex I looked at adjacent vertices and DFS went from them while counting how many vertices I go around. Then, if the number of vertices that DFS counted for each adjacent vertex of the original vertex is the same, then the original vertex is right for us. This solution gives the correct answer, but does not pass in time. I guess there is a more correct approach to the solution.

    1 answer 1

    In essence, you need a vertex, in which the sizes of all subtrees are the same. For example, for the chain is the middle. This can be done linearly with the number of vertices. Since language is not specified, I write in pseudocode. Bonus by the way you can find all such vertices.

    void dfs(int current){ size[current] = 1; // сама вершина sizePrev = -1; good = true; for (int parent : list(current) ) tmp = dfs(parent); size[current] += tmp; if (sizePrev == -1) sizePrev = tmp; else if (sizePrev != tmp) good = false; if (sizePrev != N - size[current]) good = false; if (good) ANS.add(current); return size[current]; }

    The idea is that we run a search in depth (from the root), and the result of the function is the number of vertices in the subtree. When merging, we check that all subtrees are equal and equal to the remainder from above. If so, then the top is right for us.

    Be careful not to run the function recursively, not only for descendants but also towards the root.

    • It seems in the condition there is nothing about the size? Just less, but they can not be the same as the whole graph. It turns out, we need any. - Qwertiy ♦
    • @Qwertiy well, it says it fell to a minimum of 2 graphs with an equal number of vertices in each. - pavel
    • @pavel, so you run a function from each vertex until some kind of function is available? - marka_17
    • @ marka_17 1 time from the root of the tree. - pavel
    • @pavel, so not the fact that the tree is binary. Which vertex pick root? - marka_17