Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- using System;
- using System.Collections.Generic;
- using System.Linq;
- namespace Creep
- {
- public class Edge
- {
- public int First { get; set; }
- public int Second { get; set; }
- public int Weight { get; set; }
- }
- public class Program
- {
- static void Main()
- {
- var n = int.Parse(Console.ReadLine());
- var m = int.Parse(Console.ReadLine());
- var graph = new List<Edge>();
- for (int i = 0; i < m; i++)
- {
- var input = Console.ReadLine()
- .Split(' ')
- .Select(int.Parse)
- .ToArray();
- graph.Add(new Edge
- {
- First = input[0],
- Second = input[1],
- Weight = input[2]
- });
- }
- var prev = new int[n+1];
- for (int i = 0; i < prev.Length; i++)
- {
- prev[i] = i;
- }
- var totalCost = 0;
- foreach (var edge in graph.OrderBy(x=>x.Weight))
- {
- var first = FindRoot(prev , edge.First);
- var second = FindRoot(prev, edge.Second);
- if (first==second)
- {
- continue;
- }
- prev[first] = second;
- Console.WriteLine($"{edge.First} {edge.Second}");
- totalCost += edge.Weight;
- }
- Console.WriteLine(totalCost);
- }
- private static int FindRoot(int[] prev, int node)
- {
- while (node != prev[node])
- {
- node = prev[node];
- }
- return node;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement