#!/usr/bin/env python3
"""
https://leetcode.com/problems/minimum-height-trees/
For an undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.

Format
The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels).

You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Example 1 :

Input: n = 4, edges = [[1, 0], [1, 2], [1, 3]]

        0
        |
        1
       / \
      2   3

Output: [1]
Example 2 :

Input: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]

     0  1  2
      \ | /
        3
        |
        4
        |
        5

Output: [3, 4]
Note:

According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”
The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.
"""
from collections import (
    defaultdict,
    deque,
)
#from queue import Queue
from typing import List

class Graph:

    def __init__(self, size):
        self.adj = defaultdict(list)
        self.degree = [0] * size

    def add_edge(self, v1, v2):
        self.adj[v1].append(v2)
        self.adj[v2].append(v1)
        self.degree[v1] += 1
        self.degree[v2] += 1


def find_min_height_trees(edges: List[List[int]], n) -> List[int]:
    if n == 1:
        return [0]

    g = Graph(n)
    for v1, v2 in edges:
        g.add_edge(v1, v2)

    # get all leaf vertices
    queue = deque()
    degrees = list(g.degree)
    for idx, val in enumerate(degrees):
        if val == 1:
            queue.append(idx)

    v_count = n
    #loop until vertices to process is less than 2
    while v_count > 2:
        for i in range(len(queue)):
            vertice = queue.popleft()
            v_count -= 1

            # for each neighbor, decrease its degree and
            # if it become leaf, insert into queue
            for j in g.adj[vertice]:
                degrees[j] -= 1
                if degrees[j] == 1:
                    queue.append(j)

    return list(queue)



def main():
    assert find_min_height_trees([[1, 0], [1, 2], [1, 3]], 4) == [1]
    assert find_min_height_trees([[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]], 6) == [3, 4]


if __name__ == "__main__":
    main()
