[LeetCode] 1168. Optimize Water Distribution in a Village

 Problem :  https://leetcode.com/problems/optimize-water-distribution-in-a-village/

This problem can be reduced to a Minimum Spanning Tree problem.

We may consider the cost to build well in a village is the cost to reach to this village from any other villages. So we can use greedy algorithm to get the minimum cost to visit all villages.

class Solution:
    def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:
        graph = defaultdict(list)
        
        # consider the cost of laying pipe between village 'a' and 'b'
        # as the cast to reach village 'a' from 'b' and vice versa
        for a, b, cost in pipes:
            graph[a].append((b, cost))
            graph[b].append((a, cost))
        
        visited = set()
        
        heap = []
        total = 0
        
        # consider the cost of building well in one village
        # as the cost to reach to this building from any other building
        for i in range(n):
            heapq.heappush(heap, (wells[i], i+1))
        
        # greedily find the the minimum cost to visit all villages.
        while heap and len(visited) < n:
            cost, a = heapq.heappop(heap)
            
            if a not in visited:
                total += cost
                
                visited.add(a)
                
                for b, bcost in graph[a]:
                    heapq.heappush(heap, (bcost, b))
        
        return total

[LeetCode] 863. All Nodes Distance K in Binary Tree

 Problem : https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/

It is straightforward  to use BFS to collect the nodes on distance K in the binary tree. 

To support move upward and downward simultaneously, we need to add one more pointer to point from each node to its parent node. So we convert the given binary tree to a directed graph. 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
        
        # use dfs to find parent of each nodes
        parent = {root: None}
        def dfs(node):
            for child in [node.left, node.right]:
                if child:
                    parent[child] = node
                    dfs(child)
        
        dfs(root)
        
        # start from target node and use bfs to find all nodes on distance k
        queue = deque([target])
        visited = set([target])
        
        result = []
        step = 0
        
        while queue and step <= k:
            for _ in range(len(queue)):
                node = queue.popleft()
                if step == k:
                    result.append(node.val)
                
                for nxt in [node.left, node.right, parent[node]]:
                    if nxt and nxt not in visited:
                        visited.add(nxt)
                        queue.append(nxt)
                
            step += 1
                
        return result

[LeetCode] 332. Reconstruct Itinerary

 Problem : https://leetcode.com/problems/reconstruct-itinerary/

Consider each city is a vertex in a directed graph, then every ticket is an edge between 2 vertices.

Use one hash table to track all available tickets. ( Notice : There could be duplicated tickets between 2 cities )

Then use DFS to find the possible path between city "JFK" to the ending city.

DFS ends when number of city = total number of tickets  + 1

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        graph = defaultdict(list)
        allTickets = defaultdict(int)
        
        for src, dst in tickets:
            graph[src].append(dst)
            allTickets[(src,dst)] += 1
        
        for src in graph.keys():
            graph[src].sort()
        
        
        def dfs(src, path):
            if len(path) == len(tickets) + 1:
                return path
            
            for dst in graph[src]:
                if allTickets[(src,dst)] > 0:
                    allTickets[(src,dst)] -= 1
                    
                    tmp = dfs(dst, path + [dst])
                    if tmp:
                        return tmp
                    
                    allTickets[(src,dst)] += 1
                    
            return None
        
    
        return dfs("JFK", ["JFK"])

[LeetCode] 310. Minimum Height Trees

 Problem : https://leetcode.com/problems/minimum-height-trees/

The entire process is like peeling an onion.  Keep removing vectors only has 1 edge until the graph has less than 2 vectors left. Return the remaining vectors as the root of MHTs.

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {   
        int[] degree = new int[n];
        Map<Integer, List<Integer>> graph = new HashMap();
        
        // construct the graph
        for (int i = 0; i < edges.length; i++) {
            int a = edges[i][0];
            int b = edges[i][1];
            
            if (!graph.containsKey(a)) {
                graph.put(a, new ArrayList<Integer>());
            }
            
            if (!graph.containsKey(b)) {
                graph.put(b, new ArrayList<Integer>());
            }
            
            graph.get(a).add(b);
            graph.get(b).add(a);
            
            degree[a] += 1;
            degree[b] += 1;
        }
        
        // start to peel the onion
        Queue<Integer> queue = new LinkedList();
        boolean[] deleted = new boolean[n];
        int remains = n;
        
        for (int i = 0; i < n; i++) {
            // put all nodes on outline to the queue
            if (degree[i] <= 1) {
                queue.offer(i);
            }
        }
        
        // peel the onion until less than 2 nodes are left
        // a MHT can have 2 possible roots in maximum
        while (remains > 2) {
            int size = queue.size();
            // use for-loop to ensure peel all nodes on current layer
            for (int i = 0; i < size; i++) {
                // peel the node off the tree
                int a = queue.poll();
                deleted[a] = true;
                degree[a] -= 1;
                remains -= 1;

                for (int b : graph.get(a)) {
                    if (deleted[b]) {
                        continue;
                    }

                    // put its peer to queue if the peer node is on the next layer
                    degree[b] -= 1;
                    if (degree[b] == 1) {
                        queue.offer(b);
                    }
                }
            }
        }
        
        // nodes on the last layer are MHT's root 
        return new ArrayList<Integer>(queue);
    }
}

Edited on 12/16/2021. Replace with Java solution.