Number of ways to reconstruct a tree

Array Hash Table Tree Graph Theory Simulation

45.5% acceptance

Mar 1, 2026

235

159

You are given an array pairs, where pairs[i] = [xi, yi], and: There are no duplicates. xi < yi Let ways be the number of rooted trees that satisfy the following conditions: The tree consists of nodes whose values appeared in pairs. A pair [xi, yi] exists in pairs if and only if xi is an ancestor of yi or yi is an ancestor of xi. Return: 0 if ways == 0 1 if ways == 1 2 if ways > 1

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

use std::collections::{HashMap, HashSet};

impl Solution {
  pub fn check_ways(pairs: Vec<Vec<i32>>) -> i32 {
    let mut adj: HashMap<i32, HashSet<i32>> = HashMap::new();
    for p in &pairs {
      adj.entry(p[0]).or_default().insert(p[1]);
      adj.entry(p[1]).or_default().insert(p[0]);
    }
    let n = adj.len();
    let mut nodes: Vec<i32> = adj.keys().cloned().collect();
    nodes.sort_unstable_by_key(|k| adj[k].len());

    // The graph must be connected to form a valid tree
    let start = nodes[0];
    let mut visited = HashSet::new();
    let mut stack = vec![start];
    visited.insert(start);
    while let Some(node) = stack.pop() {
      for &nb in &adj[&node] {
        if visited.insert(nb) { stack.push(nb); }
      }
    }
    if visited.len() != n { return 0; }

    let mut result = 1;
    for &u in &nodes {
      let deg_u = adj[&u].len();
      // Find parent: neighbor of u with minimum degree >= deg_u
      let par = adj[&u].iter()
        .filter(|&&v| adj[&v].len() >= deg_u)
        .min_by_key(|&&v| adj[&v].len())
        .cloned();

      match par {
        None => {
          // u is the root candidate, must have degree = n-1
          if deg_u != n - 1 { return 0; }
        }
        Some(p) => {
          let deg_p = adj[&p].len();
          // All neighbors of u (except p) must also be neighbors of p
          for &w in &adj[&u] {
            if w == p { continue; }
            if !adj[&p].contains(&w) { return 0; }
          }
          if deg_p == deg_u { result = 2; }
        }
      }
    }
    result
  }
}