Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1
[VOJ] Mã nguồn #214 - BIC-Dùng kiến thức về thành phần liên thông mạnh
Ngày: 06-06-2011
Cập nhật: 06-06-2011
Người gửi: hbt123
Ngôn ngữ: Pascal
Xem: 607

Điểm: 4.4/5 (8 Phiếu)


uses
     Math;
 
const
     inputfile  = 'BIC.INP';
     outputfile = 'BIC.OUT';
     MaxN       = 10000;
     maxM       = 100000;
     Modum      = 1000000000;
 
var
     N, M, top, component, count : longint;
     res ,ch : string[9];
     F, stack, linkV, sumV : array[1.. maxN] of longint;
     newV, headV, head : array[1.. maxn] of longint;
     ok, free : array[1.. maxN] of boolean;
     adj, link : array[1.. MaxM] of longint;
 
procedure readdate;
 var
   f : text;
   i, u : Longint;
    begin
      assign(f, inputfile); reset(f);
        readln(f, N, M);
        for u := 1 to N do head[u] := 0;
        for i := 1 to M do
          begin
            readln(f, u, adj[i]);
            link[i] := head[u];
            head[u] := i;
          end;
      close(f);
    end;
 
Procedure Push( u : longint );
 begin
   inc( top ); stack[top] := u;
 end;
 
Function pop : longint;
 begin
   pop := stack[top]; dec( top );
 end;
 
procedure InitGraph;
 var
   u : longint;
   trace, number, low : array[1.. MaxN] of longint;
 
      Procedure Tajan( u : longint);
       var
         i, v, k : longint;
          begin
            inc( count );
            number[u] := count; low[u] := count;
            push( u );
            i := head[u];
            while i <> 0 do
              begin
                v := adj[i];
                if free[v] then
                  begin
                    if trace[v] = 0 then
                      begin
                        trace[v] := u;
                        Tajan( v );
                        low[u] := Min( low[u], low[v] );
                      end
                      else low[u] := Min( low[u], number[v] );
                  end;
                i := link[i];
              end;
 
            if low[u] = number[u] then
              begin
                inc( component );
                headV[component] := 0;
                k := 0;
                repeat
                  v := pop;
                  free[v] := false;
                  linkV[v] := headV[component];
                  headV[component] := v;
                  newV[v] := component;
                  inc( k );
                until v = u;
                sumV[component] := k;
              end;
          end;
 
    begin
      for u := 1 to N do trace[u] := 0;
      for u := 1 to N do free[u] := true;
      count := 0;
      top := 0;
      component := 0;
      trace[1] := -1;
      Tajan( 1 );
    end;
 
Function Test : boolean;
 var
   u :Longint;
 
     Procedure Visit( address : longint);
      var
        u, v, i : Longint;
         begin
           free[address] := false;
           u := headV[address];
           while u <> 0 do
             begin
               i := head[u];
               while i <> 0 do
                 begin
                   v := adj[i];
                   if free[newV[v]] then Visit( newV[v]);
                   if (newV[v] = newV[2])or(ok[newV[v]]) then ok[address] := true;
                   i := link[i];
                 end;
               u := linkV[u];
             end;
           push(address);
         end;
 
    begin
      for u := 1 to N do ok[u] := false;
      for u := 1 to N do free[u] := true;
      top := 0;
      Visit( newV[1] );
      if ok[newV[1]]= false then
        begin
          ch := '0';
          exit( false );
        end;
      for u := 1 to N do if ok[u] and (sumV[u]>1) then
        begin
          ch := 'inf';
          exit( false );
        end;
 
      exit( true );
    end;
 
Procedure Process;
 var
    u, address : longint;
    print : boolean;
 
      Procedure Opimize( address : longint);
       var
         u, i, v : longint;
          begin
            u := headV[address];
            if (sumV[address] > 1)or(u=0) then exit;
            i := head[u];
            while i <> 0 do
              begin
                v := adj[i];
                f[v] := (f[u] + f[v]) ;
                if f[v] >= modum then print := true;
                f[v] := f[v] mod modum;
                i := link[i];
              end;
          end;
 
    begin
      for u := 1 to N do f[u] := 0;
      f[1] := 1;
      print := false;
      repeat
        address := pop;
        Opimize( address );
      until top = 0;
      if print = false then writeln( f[2]) else
        begin
          str(f[2], res);
          while length(res) < 9 do res := '0' + res;
          writeln( res);
        end;
    end;
 
BEGIN
  assign(output, outputfile); rewrite(output);
 
  Readdate;
  InitGraph;
  If test then process else writeln(ch);
 
  close(output);
END.