NKCITY - Xây dựng thành phố

Tác giả: RR

Ngôn ngữ: Pascal

uses math;
var
  res,u,v,i,n,m:longint;
  eu,ev,ec:array[1..10111] of longint;
  lab:array[1..10111] of longint;

procedure swap(var a,b:longint);
    var
      tmp:longint;
    begin
      tmp:=a; a:=b; b:=tmp;
    end;

procedure sort(l,r:longint);
    var
      i,j,mid:longint;
    begin
      i:=l; j:=r; mid:=ec[l+random(r-l+1)];
      repeat
        while ec[i]<mid do inc(i);
        while ec[j]>mid do dec(j);
        if i<=j then
          begin
            swap(eu[i],eu[j]);
            swap(ev[i],ev[j]);
            swap(ec[i],ec[j]);
            inc(i); dec(j);
          end;
      until i>j;
      if i<r then sort(i,r);
      if l<j then sort(l,j);
    end;

function getRoot(u:longint):longint;
    begin
      if lab[u]<0 then exit(u);
      lab[u]:=getRoot(lab[u]); exit(lab[u]);
    end;

procedure union(r1,r2:longint);
    var
      x:longint;
    begin
      x:=lab[r1]+lab[r2];
      if lab[r1]<lab[r2] then
        begin
          lab[r1]:=x;
          lab[r2]:=r1;
        end
      else
        begin
          lab[r2]:=x;
          lab[r1]:=r2;
        end;
    end;

begin
  read(n,m);
  for i:=1 to m do
    read(eu[i],ev[i],ec[i]);

  sort(1,m);
  for i:=1 to n do lab[i]:=-1;
  for i:=1 to m do
    begin
      u:=getRoot(eu[i]); v:=getRoot(ev[i]);
      if u<>v then
        begin
          res:=max(res,ec[i]);
          union(u,v);
        end;
    end;
  writeln(res);
end.

Download