# 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: EASY
Tags: Tree algorithms

Graph algorithms

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


from queue import PriorityQueue
taken = set()
adj = {}
pq = PriorityQueue()

def process(v, order):
	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


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])
				elif 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