Leetcode 1719. Number Of Ways To Reconstruct A Tree

Problem Description

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:

1. The tree consists of nodes whose values appeared in pairs.
2. A pair [xi, yi] exists in pairs if and only if xi is an ancestor of yi or yi is an ancestor of xi.

Note: the tree does not have to be a binary tree.

You need to return:

• 0 if ways == 0
• 1 if ways == 1
• 2 if ways > 1

Example

Let's go through the Example 1:

1Input: pairs = [[1,2],[2,3]]
2Output: 1

In this example, we have two pairs: [1, 2] and [2, 3]. We can try to build a rooted tree:

1    1
2   /
3  2
4 /
53

This is the only valid rooted tree that can be constructed from the given pairs. Therefore, the output is 1.

Approach

We can solve this problem using depth-first search (DFS). The idea is to build the rooted tree step by step and check if it satisfies the conditions.

1. Initialize an adjacency list to store the relationship between parent and child nodes.
2. For each pair in the input, add its parent and child node to the adjacency list.
3. For each node, create a dfs function to explore the tree and count the number of trees that satisfy the conditions.
4. In the dfs function,
   • If the current node has been visited, return 0.
   • If the current node is the last node, return 1.
   • For each child of the current node, call the dfs function recursively and add its result to the count of trees.
   • If the count is greater than 1, return 2.
   • If the count is equal to 1, return 1.
5. Return the count of rooted trees that satisfy the conditions.

Algorithm Steps

Let's manually walk through the steps of the approach using Example 1 as the input:

1. The pairs are: [[1,2],[2,3]]
2. Build the adjacency list: {1: [2], 2: [1, 3], 3: [2]}
3. Start from the minimum node (1) and call the dfs function.
4. In the dfs function:
   • The current node is 1.
   • Check its child 2.
   • Call the dfs function with the node 2.
   • In the dfs function:
     • The current node is 2.
     • Check its child 1 (already visited) and child 3.
     • Call the dfs function with the node 3.
     • In the dfs function:
       • The current node is 3.
       • As it is the last node (no children), return 1.
       • (Back to node 2) Add the result (1) to the count of trees. Now, count = 1.
     • Return the count (1).
   • (Back to node 1) Add the result (1) to the count of trees. Now, count = 1.
5. Return the count (1).

As the count is equal to 1, the output is 1.

Python Solution

1from collections import defaultdict
2
3class Solution:
4    def checkWays(self, pairs: List[List[int]]) -> int:
5        adj_list = defaultdict(list)
6        for pair in pairs:
7            adj_list[pair[0]].append(pair[1])
8            adj_list[pair[1]].append(pair[0])
9
10        min_node = min(adj_list)
11        visited = set()
12        def dfs(node):
13            visited.add(node)
14            count = 0
15            for child in adj_list[node]:
16                if child in visited:
17                    continue
18                count += dfs(child)
19                if count > 1:
20                    return 2
21            return count if count > 0 else 1
22
23        return dfs(min_node)

Java Solution

1import java.util.HashMap;
2import java.util.List;
3import java.util.Map;
4import java.util.Set;
5import java.util.HashSet;
6
7class Solution {
8    public static int checkWays(List<List<Integer>> pairs) {
9        Map<Integer, List<Integer>> adjList = new HashMap<>();
10        for (List<Integer> pair: pairs) {
11            int a = pair.get(0), b = pair.get(1);
12            adjList.putIfAbsent(a, new ArrayList());
13            adjList.putIfAbsent(b, new ArrayList());
14            adjList.get(a).add(b);
15            adjList.get(b).add(a);
16        }
17
18        int start = Integer.MAX_VALUE;
19        for (int key: adjList.keySet()) {
20            start = Math.min(start, key);
21        }
22
23        Set<Integer> visited = new HashSet<>();
24        return dfs(adjList, start, visited);
25    }
26
27    private static int dfs(Map<Integer, List<Integer>> adjList, int node, Set<Integer> visited) {
28        visited.add(node);
29        int count = 0;
30        for (int child: adjList.get(node)) {
31            if (visited.contains(child)) continue;
32            count += dfs(adjList, child, visited);
33            if (count > 1) return 2;
34        }
35        return count > 0 ? count : 1;
36    }
37}

JavaScript Solution

1class Solution {
2    static checkWays(pairs) {
3        const adjList = new Map();
4        for (const [a, b] of pairs) {
5            if (!adjList.has(a)) adjList.set(a, []);
6            if (!adjList.has(b)) adjList.set(b, []);
7            adjList.get(a).push(b);
8            adjList.get(b).push(a);
9        }
10
11        const start = Math.min(...adjList.keys());
12        const visited = new Set();
13        return this.dfs(adjList, start, visited);
14    }
15
16    static dfs(adjList, node, visited) {
17        visited.add(node);
18        let count = 0;
19        for (const child of adjList.get(node)) {
20            if (visited.has(child)) continue;
21            count += this.dfs(adjList, child, visited);
22            if (count > 1) return 2;
23        }
24        return count > 0 ? count : 1;
25    }
26}

C++ Solution

1#include <vector>
2#include <unordered_map>
3#include <unordered_set>
4#include <limits>
5using namespace std;
6
7class Solution {
8public:
9    int checkWays(vector<vector<int>>& pairs) {
10        unordered_map<int, vector<int>> adjList;
11        for (const auto& pair : pairs) {
12            int a = pair[0], b = pair[1];
13            adjList[a].push_back(b);
14            adjList[b].push_back(a);
15        }
16
17        int start = numeric_limits<int>::max();
18        for (const auto& kv : adjList) {
19            start = min(start, kv.first);
20        }
21
22        unordered_set<int> visited;
23        return dfs(adjList, start, visited);
24    }
25
26private:
27    int dfs(unordered_map<int, vector<int>>& adjList, int node, unordered_set<int>& visited) {
28        visited.insert(node);
29        int count = 0;
30        for (int child : adjList[node]) {
31            if (visited.count(child)) continue;
32            count += dfs(adjList, child, visited);
33            if (count > 1) return 2;
34        }
35        return count > 0 ? count : 1;
36    }
37};

C# Solution

1using System;
2using System.Collections.Generic;
3
4public class Solution {
5    public int CheckWays(int[][] pairs) {
6        var adjList = new Dictionary<int, List<int>>();
7        foreach (var pair in pairs) {
8            int a = pair[0], b = pair[1];
9            if (!adjList.ContainsKey(a)) adjList[a] = new List<int>();
10            if (!adjList.ContainsKey(b)) adjList[b] = new List<int>();
11            adjList[a].Add(b);
12            adjList[b].Add(a);
13        }
14
15        int start = int.MaxValue;
16        foreach (int key in adjList.Keys) {
17            start = Math.Min(start, key);
18        }
19
20        var visited = new HashSet<int>();
21        return DFS(adjList, start, visited);
22    }
23
24    private int DFS(Dictionary<int, List<int>> adjList, int node, HashSet<int> visited) {
25        visited.Add(node);
26        int count = 0;
27        foreach (int child in adjList[node]) {
28            if (visited.Contains(child)) continue;
29            count += DFS(adjList, child, visited);
30            if (count > 1) return 2;
31        }
32        return count > 0 ? count : 1;
33    }
34}

Conclusion

In conclusion, we have implemented the solution using depth-first search (DFS) in Python, JavaScript, Java, C++, and C#. Our goal was to find the number of rooted trees that satisfy the conditions given in the problems. We used adjacency lists to represent the input pairs as a graph and then searched the graph using DFS. By leveraging DFS and careful counting, we arrived at the correct output for each input.

Remember to analyze the problem and explore its details thoroughly first. Then, choose the appropriate data structures and algorithms to solve it. For this particular problem, DFS was an effective technique to traverse the graph and find possible rooted trees. Overall, this problem reinforces the importance of understanding graph traversal and the DFS algorithm.