题干中描述的是否认为POPULAr 其实就是可以理解成是否可以到达，那么久联想到了floodfill，但是在读入数据的时候，预处理(连边的时候应该反向连边）。
  下面就是直接的水水的floodfill了·。 
 附上丑陋的代码，供众牛鄙视(没有思维复杂度，没有代码复杂度)
  program poj2186;
var e,e2:array[0..50000] of record
       x,y,n:longint;
    end;
    f,f1:array[0..10000] of longint;
    o,n,m,i,a,b,tot,sum,biao,o1:longint;
    v:array[0..10000] of boolean;
procedure add2(a,b:longint);
begin
  inc(o1);
  e2[o1].x:=a;
  e2[o1].y:=b;
  e2[o1].n:=f1[a];
  f1[a]:=o;
end;
procedure add(a,b:longint);
begin
  inc(o);
  e[o].x:=a;
  e[o].y:=b;
  e[o].n:=f[a];
  f[a]:=o;
end;
procedure dfs2(x:longint);
var t:longint;
begin
  v[x]:=true;
  t:=f1[x];
  while t<>0 do
    begin
      if v[e2[t].y]=false then
        begin
          inc(tot);
          dfs2(e2[t].y);
        end;
      t:=e2[t].n;
    end;
end;
procedure dfs(x:longint);
var t:longint;
begin
  v[x]:=true;
  t:=f[x];
  while t<>0 do
    begin
      if v[e[t].y]=false then
        begin
          inc(tot);
          dfs(e[t].y);
        end;
      t:=e[t].n;
    end;
end;
begin
  assign(input,'poj2186.in');reset(input);
  assign(output,'poj2186.out');rewrite(output);
  readln(n,m);
  for i:= 1 to m do
    begin
      readln(a,b);
      add(b,a);
      add2(a,b);
    end;
  for i:= 1 to n do
    begin
      fillchar(v,sizeof(v),false);
      tot:=0;
      dfs(i);
      if tot=n-1 then begin biao:=i; break; end;
    end;
  if biao=0 then writeln(0) else
    begin
      tot:=0;
      fillchar(v,sizeof(v),false);
      dfs2(biao);
      writeln(tot+1);
    end;
  close(input);
  close(output);
end.

• Re:强连通分量代码复杂度太高了，直接floodfill 300MS水过 (29) MaoJK 2012-07-31 10:03:35
  • Re:强连通分量代码复杂度太高了，直接floodfill 300MS水过 (47) yomean 2012-11-10 21:26:41