VCOLDWAT - Nước lạnh

Tác giả: flashmt

Ngôn ngữ: Pascal

const max=100000;
var n,m:longint;
    a:array[0..max,0..2] of longint;
    d,q:array[1..max] of longint;

procedure rf;
var i:longint;
begin
     readln(n,m);
     for i:=1 to m do readln(a[i,0],a[i,1],a[i,2]);
end;

procedure sort(l,r:longint);
var i,j,x:longint;
begin
     i:=l; j:=r; x:=a[(i+j) div 2,0];
     repeat
           while a[i,0]<x do i:=i+1;
           while x<a[j,0] do j:=j-1;
           if i<=j then
           begin
                a[0]:=a[i]; a[i]:=a[j]; a[j]:=a[0];
                i:=i+1; j:=j-1;
           end;
     until i>j;
     if i<r then sort(i,r);
     if j>l then sort(l,j);
end;

function bs(p:longint):longint;
var l,r,mid:longint;
begin
     l:=1; r:=m;
     repeat
           mid:=(l+r) div 2;
           if a[mid,0]=p then break
           else
           begin
                if a[mid,0]<p then l:=mid+1
                else r:=mid-1;
           end;
     until l>r;
     if l>r then bs:=0
     else bs:=mid;
end;

procedure pr;
var i,j,num,c,t:longint;
begin
     sort(1,m);
     fillchar(d,sizeof(d),0);
     d[1]:=1;
     i:=a[1,1]; j:=a[1,2];
     d[i]:=2; d[j]:=2;
     q[1]:=i; q[2]:=j;
     num:=2; c:=1;
     repeat
           t:=bs(q[c]);
           if t>0 then
           begin
                q[num+1]:=a[t,1]; q[num+2]:=a[t,2];
                d[a[t,1]]:=d[q[c]]+1;
                d[a[t,2]]:=d[a[t,1]];
                num:=num+2;
           end;
           inc(c);
     until (c>num) or (num=n-1);
end;

procedure wf;
var i:longint;
begin
     for i:=1 to n do writeln(d[i]);
end;

begin
     rf;
     pr;
     wf;
end.

Download