We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Even Tree
  5. Discussions

Even Tree

  • mah_shamim
     + 0 comments

    Approach

    1. Use a Depth First Search (DFS) to calculate the size of each subtree.
    2. Count the number of subtrees with even numbers of nodes.
    3. The number of edges to remove is the number of even subtrees minus 1 (since we don't count the root's subtree).

    Solution

    Here is the PHP code:

    <?php

function evenForest($t_nodes, $t_edges, $t_from, $t_to) {
    $graph = [];
    // Initialize graph
    for ($i = 1; $i <= $t_nodes; $i++) {
        $graph[$i] = [];
    }

    // Build adjacency list
    for ($i = 0; $i < count($t_from); $i++) {
        $graph[$t_from[$i]][] = $t_to[$i];
        $graph[$t_to[$i]][] = $t_from[$i];
    }

    // Array to store the size of each subtree
    $subtreeSize = array_fill(1, $t_nodes, 0);

    function dfs($node, $parent, &$graph, &$subtreeSize) {
        $subtreeSize[$node] = 1; // Include the node itself
        foreach ($graph[$node] as $neighbor) {
            if ($neighbor != $parent) {
                $subtreeSize[$node] += dfs($neighbor, $node, $graph, $subtreeSize);
            }
        }
        return $subtreeSize[$node];
    }

    // Start DFS from node 1 (arbitrary choice for the root)
    dfs(1, -1, $graph, $subtreeSize);

    $removableEdges = 0;

    // Count removable edges
    for ($i = 2; $i <= $t_nodes; $i++) {
        if ($subtreeSize[$i] % 2 == 0) {
            $removableEdges++;
        }
    }

    return $removableEdges;
}

// Example usage:
$t_nodes = 10;
$t_edges = 9;
$t_from = [2, 3, 4, 5, 6, 7, 8, 9, 10];
$t_to = [1, 1, 2, 2, 3, 3, 4, 4, 5];

echo evenForest($t_nodes, $t_edges, $t_from, $t_to); // Output should be 2

?>

    Explanation:

    1. Graph Construction: We use an adjacency list to represent the graph.
    2. DFS Traversal: We traverse the graph using DFS, calculating the size of each subtree.
    3. Subtree Size Calculation: The size of each subtree is stored in the $subtreeSize array.
    4. Count Removable Edges: We iterate through each node (except the root) and count subtrees of even size.

    This solution assumes that the tree is given in a 1-based index as in the example. If your tree nodes are 0-based, you should adjust the code accordingly.