Connecting Mars

Problem Statement:

The Democratic Sovereign People’s Republic of Mars is very corrupt. Five years ago, the government promised to build big highways connecting every major city on Mars but they have still not delivered on that promise. The people are now protesting about the poor transportation infrastructure, so the government has finally decided to build the roads. However, the president wants to keep all the taxpayers money for himself, and he plans on spending as little money as possible to build the roads. To help him out, he wants you to find the least amount of money required to connect every city on Mars.

There are N cities on Mars and M potential roads that can be built between these cities. For each potential road, you are given 3 integers, the starting city, the ending city and the cost to build that road. The roads are bidirectional, i.e. the road used to travel from city U to city V can also be used to travel from city V to city U.

Constraints:

• 1 ≤ M ≤ min(10⁵, N * (N + 1) / 2)
• 0 ≤ U_i, V_i ≤ N
• 0 ≤ W_i ≤ 10⁹

Subtask 1: 20 points

• 1 ≤ N ≤ 15

Subtask 2: 30 points

• 1 ≤ N ≤ 100

Subtask 3: 50 points

• 1 ≤ N ≤ 10⁵

Input Format:

• The first line contains two integers N and M (N is the number of cities, M is the number of maximum possible roads)
• The next M lines contain three integers U_i, V_i and W_i, representing one road (U_i is the starting city, V_i is the ending city and W_i is the cost of building the road)

Output Format:

• Print a single line for each testcase containing the least amount of money required to connect all the cities. If the cities cannot be connected print -1

Sample input:

3 4
1 3 5
3 2 6
1 2 2
3 1 9

Sample output:

7

Explanation:

We can build a road between cities 1 and 3, and a road between cities 1 and 2, for a total cost of 5 + 2 = 7

Note that cities 3 and 2 need not have a direct road between them, they are still considered connected as one can travel from 3 to 1 to 2.

Solution:

n, m = map(int, input().split())
a = [-1] * n
e = [list(map(int, input().split())) for _ in range(m)]

def get(x):
	if a[x] < 0:
		return x
	a[x] = get(a[x])
	return a[x]

def unite(x, y):
	x = get(x)
	y = get(y)

	if x == y:
		return False
	
	if a[x] < a[y]:
		x, y = y, x
	
	a[y] += a[x]
	a[x] = y
	return True

e.sort(key = lambda x: x[2])

res = 0
for u, v, w in e:
	if unite(u - 1, v - 1):
		res += w
x = get(0)
for i in range(1, n):
	if get(i) != x:
		print(-1)
		break
else:
	print(res)