# Idea

In the world of graphs exists a structure called "spanning tree". It is unique because it's created not on its own, but based on other graphs. To make a spanning tree out of a given graph you should remove all the edges which create cycles, for example:
```
This can become      this      or      this        or       this

 A                    A                  A                   A
 |\                   |                   \                  |\
 | \       ==>        |                    \                 | \
 |__\                 |__                 __\                |  \
B   C                 B  C               B  C                B  C
```
Each *edge* (line between 2 *vertices*, i.e. points) has a weight, based on which you can build minimum and maximum spanning trees (sum of weights of vertices in the resulting tree is minimal/maximal possible).  
[Wikipedia article](https://en.wikipedia.org/wiki/Spanning_tree) on spanning trees, in case you need it.

___

# Task

You will receive an array like this: `[["AB", 2], ["BC", 4], ["AC", 1]]` which includes all edges of an arbitrary graph and a string `"min"`/`"max"`. Based on them you should get and return a new array which includes only those edges which form a minimum/maximum spanning trees.
```python
edges = [("AB", 2), ("BC", 4), ("AC", 1)]

make_spanning_tree(edges, "min")    ==>    [("AB", 2), ("AC", 1)]
make_spanning_tree(edges, "max")    ==>    [("AB", 2), ("BC", 4)]
```

___

# Notes

* All vertices will be connected with each other
* You may receive cycles, for example - `["AA", n]`
* The subject of the test are these 3 values: number of vertices included, total weight, number of edges, but **you should not return them**, there's a special function which will analyze your output instead

Difficulty: introductory

Starter code:

def make_spanning_tree(edges, t):
	

Solutions:
from operator import itemgetter
from numpy import delete

def make_spanning_tree(edges, t):
    memo, result = [], []
    for v in sorted(edges, key=itemgetter(1), reverse=(t=="max")):
        (x,y), w = v
        
        if x == y: continue
        
        i = next((i for i,s in enumerate(memo) if x in s), None)
        j = next((j for j,s in enumerate(memo) if y in s), None)
        
        if i == j != None: continue
            
        result.append(v)
        
        if i == j: memo.append({x, y})
        elif i is None: memo[j].add(x)
        elif j is None: memo[i].add(y)
        else:
            memo.append(memo[i] | memo[j])
            memo = delete(memo, [i, j]).tolist()

    return result

def make_spanning_tree(edges, t):
    edges = sorted(edges, key=lambda x:x[1], reverse=t=='max')
    span, vert = [], {}
    
    for edge in edges:
        ((a,b),_), (subA,subB) = edge, map(vert.get, edge[0])
        
        if a==b or subA is not None and subA is subB:
            continue
        
        if subA and subB:
            subA |= subB
            for v in subB: vert[v] = subA
        else:
            subSpan = subA or subB or set()
            for v in (a,b):
                subSpan.add(v)
                vert[v] = subSpan
        span.append(edge)
        
    return span

from operator import lt, gt

def mst(edges, inf, compare, min_max):
    Q = {v for vs, _ in edges for v in vs}
    C = dict.fromkeys(Q, inf)
    E = dict.fromkeys(Q)
    while Q:
        v = min_max(Q, key=C.get)
        Q.discard(v)
        candidates = ((edge, weight) for edge, weight in edges if v in edge)
        for edge, weight in candidates:
            v_, w = edge
            if w == v:
                w = v_
            if w in Q and compare(weight, C[w]):
                E[w], C[w] = edge, weight
        if E[v] is not None:
            yield E[v], C[v]

def make_spanning_tree(edges, t):
    return list(mst(
        edges,
        float('inf' if t == 'min' else '-inf'),
        lt if t == 'min' else gt,
        min if t == 'min' else max,
    ))

def make_spanning_tree(edges, t):
    id = {}
    edges.sort(key=lambda x: x[1], reverse=t == 'max')
    spanning_tree = []
    for (u, v), cost in edges:
        if u not in id: id[u] = u
        if v not in id: id[v] = v
        if id[u] != id[v]:
            id = {x: y if y != id[v] else id[u] for x, y in id.items()}
            spanning_tree.append((u + v, cost))
    return spanning_tree

def make_spanning_tree(edges, t):
    edges.sort(reverse=True)
    last_node = ord(edges[0][0][0]) - 65
    edges.sort()
    edges.sort(key=lambda edges: edges[1])

    if(t == 'max'):
        edges.reverse()
    
    nonlocal parent
    parent = [int(x) for x in range(last_node+10000)]
    result = []

    for edge in edges:
        startNode = ord(edge[0][0])-65
        endnode = ord(edge[0][1])-65

        if(Find(startNode) != Find(endnode)):
            Union(startNode, endnode)
            result.append(edge)

    return result

def Find(x):
    if(x == parent[x]):
        return x
    else:
        p = Find(parent[x])
        parent[x] = p
        return p

def Union(x, y):
    x = Find(x)
    y = Find(y)

    if(x != y):
        parent[y] = x

class DisjointSet:
    def __init__(self):
        self.data = {}
        
    def add_node(self, v):
        self.data[v] = v
        
    def find(self, v):
        if (self.data[v] == v):
            return v
        else :
            return self.find(self.data[v])
        
    def union(self, v, w):
        root_v = self.find(v)
        root_w = self.find(w)
        
        self.data[root_v] = root_w
        
    def in_same_set(self, v, w):
        root_v = self.find(v)
        root_w = self.find(w)
        
        return root_v == root_w

def make_spanning_tree(edges, t):
    edges = sorted(edges, key=lambda x: x[1], reverse = t == 'max')    
    tree = DisjointSet()
    output = []
        
    while (edges):
        edge = edges.pop(0)
        v, w = edge[0][0], edge[0][1]
        if (v not in tree.data.keys()):
            tree.add_node(v)
        if (w not in tree.data.keys()):
            tree.add_node(w)
            
        if (not tree.in_same_set(v, w)):
            tree.union(v, w)
            output.append(edge)
            
    return output

class DisjointSet:
    def __init__(self):
        self.data = {}
        
    def add_node(self, v):
        self.data[v] = v
        
    def find(self, v):
        if (self.data[v] == v):
            return v
        else :
            return self.find(self.data[v])
        
    def union(self, v, w):
        root_v = self.find(v)
        root_w = self.find(w)
        
        self.data[root_v] = root_w
        
    def in_same_set(self, v, w):
        root_v = self.find(v)
        root_w = self.find(w)
        
        return root_v == root_w

def make_spanning_tree(edges, t):
    if (t == 'min'):
        edges = sorted(edges, key=lambda x: x[1])    
    elif (t == 'max'):
        edges = sorted(edges, key=lambda x: -x[1])
        
    
    tree = DisjointSet()
    for edge in edges:
        v, w = edge[0][0], edge[0][1]
        if (v not in tree.data.keys()):
            tree.add_node(v)
        if (w not in tree.data.keys()):
            tree.add_node(w)
    cnt = 0
    output = []
    while (cnt < len(tree.data)-1):
        edge = edges.pop(0)
        v, w = edge[0][0], edge[0][1]
        
        if (not tree.in_same_set(v, w)):
            tree.union(v, w)
            output.append(edge)
            cnt += 1
            
    return output

from queue import PriorityQueue

taken = set()
adj = {}
pq = PriorityQueue()


def process(v, order):
    # order to be 1 or -1 to sort the priority_queue
    taken.add(v)
    for vi, w in adj[v]:
        if not vi in taken:
            pq.put((order * w, vi, v))


def make_spanning_tree(edges, t):
    edges_set = set()
    result = []
    adj.clear()
    taken.clear()
    first = ''
    order = 1 if t == 'min' else -1
    for edge in edges:
        u, v = edge[0]
        edges_set.add(edge)
        w = edge[1]
        if u == v:
            continue
        if not u in adj:
            adj[u] = []
        if not v in adj:
            adj[v] = []
        adj[u].append((v, w))
        adj[v].append((u, w))
        if not first:
            first = u

    process(first, order)
    mst_cost = 0
    while not pq.empty():
        w, u, v = pq.get()
        w = order * w
        if not u in taken:
            mst_cost += w
            process(u, order)
            result.append((v + u, w))
    for ri in range(len(result)):
        r = result[ri]
        if not r in edges_set:
            result[ri] = r[0][1] + r[0][0], r[1]
            

    return result  # vertices of a spanning tree



def filtering(lst):
    new_lst = set()
    vertices = []
    for item in lst:
        if item[0][0] not in vertices:
            vertices.append(item[0][0])
        if item[0][1] not in vertices:
            vertices.append(item[0][1])
        if item[0][0] == item[0][1]:
            continue
        else:
            new_lst.add(item)
    return [new_lst, vertices]
    
def poss_edg_func(vert, edges):
    res = []
    for edge in edges:
        if edge[0][0] in vert and edge[0][1] not in vert:
            res.append(edge)
        if edge[0][1] in vert and edge[0][0] not in vert:
            res.append(edge)
    return res
            
def make_spanning_tree(edges, t):
    temp = filtering(edges)
    edg, vert = temp[0], temp[1]
    path = [eval(t)(edg, key = lambda x: x[1])]
    while len(path) != len(vert) - 1:
        used_vert = set([char for v in path for char in v[0]])
        poss_edg = poss_edg_func(used_vert, edg)
        path.append(eval(t)(poss_edg, key = lambda x: x[1]))
    return path
        
    
    


def make_spanning_tree(edges, t):
    X = [edges[0][0][0]]
    output = []
    while True:
        val = float("inf") if t == "min" else -float("inf")
        current = new_X = None
        for node in X:
            for edge in edges:
                if t == "min":
                    if edge[0][0] == node:
                        if edge[1] <= val and edge[0][1] not in X:
                            val, current, new_X = edge[1], edge, edge[0][1]
                    elif edge[0][1] == node:
                        if edge[1] <= val and edge[0][0] not in X:
                            val, current, new_X = edge[1], edge, edge[0][0]
                else:
                    if edge[0][0] == node:
                        if edge[1] >= val and edge[0][1] not in X:
                            val, current, new_X = edge[1], edge, edge[0][1]
                    elif edge[0][1] == node:
                        if edge[1] >= val and edge[0][0] not in X:
                            val, current, new_X = edge[1], edge, edge[0][0]
        if new_X is None: break
        X.append(new_X)
        output.append(current)
    return output