Advertisement
IvetValcheva

02. Creep

Oct 8th, 2022
768
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 2.00 KB | None | 0 0
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4.  
  5. namespace Creep
  6. {
  7.    
  8.         public class Edge
  9.         {
  10.  
  11.             public int First { get; set; }
  12.  
  13.             public int Second { get; set; }
  14.  
  15.             public int Weight { get; set; }
  16.         }
  17.  
  18.  
  19.         public class Program
  20.         {
  21.             static void Main()
  22.             {
  23.  
  24.                 var n = int.Parse(Console.ReadLine());
  25.                 var m = int.Parse(Console.ReadLine());
  26.  
  27.                 var graph = new List<Edge>();
  28.                 for (int i = 0; i < m; i++)
  29.                 {
  30.                     var input = Console.ReadLine()
  31.                         .Split(' ')
  32.                         .Select(int.Parse)
  33.                         .ToArray();
  34.                     graph.Add(new Edge
  35.                     {
  36.                         First = input[0],
  37.                         Second = input[1],
  38.                         Weight = input[2]
  39.                     });
  40.                 }
  41.  
  42.                 var prev = new int[n+1];
  43.                 for (int i = 0; i < prev.Length; i++)
  44.                 {
  45.                     prev[i] = i;
  46.                 }
  47.                 var totalCost = 0;
  48.                
  49.                 foreach (var edge in graph.OrderBy(x=>x.Weight))
  50.                 {
  51.                     var first = FindRoot(prev , edge.First);
  52.                     var second = FindRoot(prev, edge.Second);
  53.  
  54.                     if (first==second)
  55.                     {
  56.                         continue;
  57.                     }
  58.  
  59.                     prev[first] = second;
  60.                     Console.WriteLine($"{edge.First} {edge.Second}");
  61.                     totalCost += edge.Weight;
  62.                 }
  63.  
  64.                 Console.WriteLine(totalCost);
  65.             }
  66.  
  67.         private static int FindRoot(int[] prev, int node)
  68.         {
  69.             while (node != prev[node])
  70.             {
  71.                 node = prev[node];
  72.             }
  73.  
  74.             return node;
  75.         }
  76.     }
  77. }
  78.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement