fork download
copy 
  1. {+--------------------------------------------------------------------------+}
  2. {|        The Textbook in Data Structure, Algorithms and Programming        |}
  3. {|              http://w...content-available-to-author-only...c.jp/~hoangle/DSAPTextbook/               |}
  4. {|                                                                          |}
  5. {|    Program: Finding_the_Minimum_Spanning_Tree_using_Kruskal_Algorithm    |}
  6. {|                         Written by Le Minh Hoang                         |}
  7. {|                      Email: dsaptextbook@gmail.com                       |}
  8. {+--------------------------------------------------------------------------+}
  9.  
  10. {$MODE DELPHI} (*This program uses 32-bit Integer [-2^31 .. 2^31 - 1]*)
  11. program Finding_the_Minimum_Spanning_Tree_using_Kruskal_Algorithm;
  12. (*
  13. IMPORTANT NOTES FOR COMPATIBILITY:
  14. ==================================
  15. - This program is especially written for running under Windows 32 bit and
  16.   Free Pascal IDE. Therefore, 32-bit Integer type is used to result in the
  17.   best performance with the {$MODE DELPHI} compiler directive of FPK for
  18.   Windows.
  19. - If you use Borland Turbo Pascal 7 for DOS, you may have to reduce the
  20.   data structure to deal with the limited memory. In addition, BP7 does not
  21.   support 32-bit Integer type, it causes some Integer variables would have
  22.   to be converted into LongInt variables.
  23. - If you prefer to compile under Delphi, you can simply convert the source
  24.   code as follows:
  25.   + Replace the type "Text" with the type "TextFile"
  26.   + Change all procedure calls "Assign(., .)" to "AssignFile(., .)" and
  27.     "Close(.)" to "CloseFile(.)"
  28.   + Remove the {$MODE DELPHI} and add the {$APPTYPE CONSOLE} compiler 
  29.     directive to the beginning of this program
  30. -----------------------------------------------------------------
  31. Please report any errors to: dsaptextbook@gmail.com, MANY THANKS!
  32. -----------------------------------------------------------------
  33. *)
  34. const
  35.   InputFile  = '';
  36.   OutputFile = '';
  37.   maxV = 1000;
  38.   maxE = (maxV - 1) * maxV div 2;
  39. type
  40.   TEdge = record    			
  41.     u, v, c: Integer;		
  42.     Mark: Boolean;			
  43.   end;
  44. var
  45.   e: array[1..maxE] of TEdge; 			
  46.   Lab: array[1..maxV] of Integer;		
  47.   n, m: Integer;
  48.   Connected: Boolean;
  49.  
  50.  
  51. procedure PrintResult;
  52. var
  53.   i, Count, W: Integer;
  54.   f: Text;
  55. begin
  56.   Assign(f, OutputFile); Rewrite(f);
  57.   if not Connected then
  58.     WriteLn(f, 'Error: Graph is not connected')
  59.   else
  60.     begin
  61.       WriteLn(f, 'Minimum spanning tree: ');
  62.       Count := 0;
  63.       W := 0;
  64.       for i := 1 to m do								
  65.         with e[i] do
  66.           begin
  67.             if Mark then								
  68.               begin
  69.                 WriteLn(f, '(', u, ', ', v, ') = ', c);
  70.                 Inc(Count);
  71.                 W := W + c;
  72.               end;
  73.             if Count = n - 1 then Break;		
  74.           end;
  75.       WriteLn(f, 'Weight = ', W);
  76.     end;
  77.   Close(f);
  78. end;
  79.  
  80. begin
  81.   PrintResult;
  82. end.
  83.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
7 21
1 2 547152
1 3 509157
1 4 539282
1 5 541645         
1 6 458433
1 7 385173

2 3 131528
2 4 92735
2 5 150511
2 6 94440
2 7 194542
3 4 216600
3 5 272401
3 6 157176
3 7 124077
4 5 57785
4 6 97323
4 7 242232
5 6 136663
5 7 283862
6 7 147426
stdout
copy 
Error: Graph is not connected
https://ideone.com/KSJG2E
language:
Pascal (fpc 3.0.4)
created:
7 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!