NKONEARC - Mạng máy tính

Tác giả: flashmt

Ngôn ngữ: Pascal

const fi='';
      fo='';
      maxn=2005;
      maxm=30005;
var n,sm,m,dem,last,re,ri,rj,ne,nf:longint;
    a:array[1..maxn,1..maxn] of boolean;
    b:array[1..maxm,0..1] of longint;
    free,e,f:array[1..maxn] of boolean;
    low,num,d,st:array[1..maxn] of longint;

procedure rf;
var i,x,y:longint;
begin
     assign(input,fi); reset(input);
     readln(n,m);
     for i:=1 to m do
     begin
          readln(b[i,0],b[i,1]);
          a[b[i,0],b[i,1]]:=true;
     end;
     for i:=1 to n do free[i]:=true;
     close(input);
end;

function pop:longint;
begin
     pop:=st[last];
     dec(last);
end;

procedure push(i:longint);
begin
             inc(last);
     st[last]:=i;
end;

function min(u,v:longint):longint;
begin
     if u<v then min:=u else min:=v;
end;

procedure visit(x:longint);
var i:longint;
begin
     inc(dem); num[x]:=dem; low[x]:=dem;
     push(x);
     for i:=1 to n do
         if free[i] and a[x,i] then
            if num[i]>0 then low[x]:=min(low[x],num[i])
            else
            begin
                 visit(i);
                 low[x]:=min(low[x],low[i]);
            end;
     if num[x]=low[x] then
     begin
          inc(sm); d[x]:=sm;
          repeat
                i:=pop;
                free[i]:=false;
                d[i]:=sm;
          until i=x;
     end;
end;

procedure pr;
var i,j,t,u,v:longint;
begin
     for i:=1 to n do
         if free[i] then visit(i);
     if sm=1 then
     begin
          for i:=1 to n do
              for j:=1 to n do
                  if (i<>j) and not a[i,j] then
                  begin
                       ri:=i; rj:=j;
                  end;
          exit;
     end;
     for i:=1 to m do
     begin
          if d[b[i,0]]=d[b[i,1]] then continue;
          if not e[d[b[i,0]]] then
          begin
               e[d[b[i,0]]]:=true;
               inc(ne);
          end;
          if not f[d[b[i,1]]] then
          begin
               f[d[b[i,1]]]:=true;
               inc(nf);
          end;
     end;
     if (ne=sm-1) and (nf=sm-1) then
     begin
          for u:=1 to n do
              if not e[u] then break;
          for ri:=1 to n do
              if d[ri]=u then break;
          for v:=1 to n do
              if not f[v] then break;
          for rj:=1 to n do
              if d[rj]=v then break;
     end
     else re:=1;
end;

procedure wf;
begin
     assign(output,fo); rewrite(output);
     if re=1 then writeln('NO')
     else
     begin
          writeln('YES');
          writeln(ri,' ',rj);
     end;
     close(output);
end;

begin
     rf;
     pr;
     wf;
end.

Download