POJ 2186（有向图的强连通分量）

题目大意：给有向图G，求图G中有多少点能从所有起点到达

暴搜必T，故本题需要用Tarjen求有向图的强连通分量。

缩点后得DAG（若有环则属同一强连通分量）

由于无环，故这图为树或树的森林

先判断图是否连通，若为森林则无解

否则，判定每个SSC是否有连出的边（由于图无环,故连出的边上的点无法回去）

答案即为出度为0的连通分量上的点

如果不止一个这样的点，则不同的点无法互相到达

Program P2186;
const
   maxn=10000;
   maxm=50000;
var
   head,edge,tail:array[1..maxm] of longint;
   sizeedge:longint;


   n,m,i,j,x,y:longint;
   ssc,c,dfs,low,outdegree,stack:array[1..maxn] of longint;
   time,size:longint;
   totssc:longint;

procedure addedge(u,v:longint);
begin
   inc(sizeedge);
   edge[sizeedge]:=v;
   tail[sizeedge]:=head[u];
   head[u]:=sizeedge;

end;


function min(a,b:longint):longint;
begin
   if a<b then exit(a) else exit(b);
end;
procedure tarjen(k,father:longint);
var
   i,j,p:longint;
begin
   inc(time);
   dfs[k]:=time;low[k]:=time;
   c[k]:=1;
   inc(size);stack[size]:=k;

   p:=head[k];
   while (p<>0) do
   begin
      i:=edge[p];

      if (dfs[k]>dfs[i]) then
      begin
         if c[i]=0 then
         begin
            tarjen(i,k);
            low[k]:=min(low[k],low[i]);
         end
         else if c[i]=1 then low[k]:=min(low[k],dfs[i]);
      end;
      p:=tail[p];

   end;
   if low[k]=dfs[k] then
   begin
      inc(totssc);
      repeat
         i:=stack[size];
         dec(size);
         c[i]:=2;
         ssc[i]:=totssc;
      until ((size=0) or (i=k));

   end;
end;
function main:longint;
var
   i,j,tot,node,p:longint;
begin
   fillchar(dfs,sizeof(dfs),0);
   fillchar(low,sizeof(low),0);
   fillchar(c,sizeof(c),0);
   fillchar(outdegree,sizeof(outdegree),0);
   time:=0;
   totssc:=0;
   for i:=1 to n do
      if (dfs[i]=0) then
      begin
         fillchar(stack,sizeof(stack),0);
         size:=0;
         tarjen(i,0);
      end;

   for i:=1 to n do
   begin
      p:=head[i];
      while (p<>0) do
      begin
         j:=edge[p];

         if (ssc[i]<>ssc[j]) then
         begin
            inc(outdegree[ssc[i]]);
         end;
         p:=tail[p];


      end;
   end;

   node:=0;
   for i:=1 to totssc do
      if outdegree[i]=0 then
      begin
         if node<>0 then exit(0);
         node:=i;
      end;
   tot:=0;
   for i:=1 to n do
      if ssc[i]=node then inc(tot);
   exit(tot);


end;
begin
   sizeedge:=0;
   fillchar(head,sizeof(head),0);
   fillchar(tail,sizeof(tail),0);
   fillchar(edge,sizeof(edge),0);
   read(n,m);
   for i:=1 to m do
   begin
      read(x,y);
      addedge(x,y);
   end;
   writeln(main);
end.