bzoj1093[ZJOI2007]最大半连通子图（tarjan+拓扑排序+dp）

Description

　　一个有向图G=(V,E)称为半连通的(Semi-Connected)，如果满足：?u,v∈V，满足u→v或v→u，即对于图中任意
两点u，v,存在一条u到v的有向路径或者从v到u的有向路径。若G'=(V',E')满足V'?V，E'是E中所有跟V'有关的边，
则称G'是G的一个导出子图。若G'是G的导出子图，且G'半连通，则称G'为G的半连通子图。若G'是G所有半连通子图
中包含节点数最多的，则称G'是G的最大半连通子图。给定一个有向图G，请求出G的最大半连通子图拥有的节点数K
，以及不同的最大半连通子图的数目C。由于C可能比较大，仅要求输出C对X的余数。

Input

　　第一行包含两个整数N，M，X。N，M分别表示图G的点数与边数，X的意义如上文所述接下来M行，每行两个正整
数a, b，表示一条有向边(a, b)。图中的每个点将编号为1,2,3…N，保证输入中同一个(a,b)不会出现两次。N ≤1
00000, M ≤1000000；对于100%的数据， X ≤10^8

Output

　　应包含两行，第一行包含一个整数K。第二行包含整数C Mod X.

Sample Input

6 6 20070603
1 2
2 1
1 3
2 4
5 6
6 4

Sample Output

3
3

先用tarjan将强连通分量缩点，然后答案就是最长路，拓扑排序+dp就可，要求方案总数，只要在dp的时候搞一搞，记录方案数就好了。

我是参考hzwer大佬的，在此表示感谢。

 program semi(input,output);

 type

   etype=record

      t,next:longint;

   end;

 var

   e,c:array[..]of etype;

   last,dfn,low,q,hav,belong,r,a,f,g,vis:array[..]of longint;

   inq:array[..]of boolean;

   n,m,p,i,j,u,v,cnt,tot,top,h,t,max,ans:longint;

 procedure add(u,v:longint);

 begin

    inc(cnt);e[cnt].t:=v;e[cnt].next:=last[u];last[u]:=cnt;

 end;

 procedure tarjan(k:longint);

 var

   i:longint;

 begin

    inc(cnt);dfn[k]:=cnt;low[k]:=cnt;

    inc(top);q[top]:=k;inq[k]:=true;

    i:=last[k];

    while i<> do

      begin

         if dfn[e[i].t]= then begin tarjan(e[i].t);if low[e[i].t]<low[k] then low[k]:=low[e[i].t]; end

         else if inq[e[i].t] and (dfn[e[i].t]<low[k]) then low[k]:=dfn[e[i].t];

         i:=e[i].next;

      end;

    if low[k]=dfn[k] then

       begin

          inc(tot);hav[tot]:=;

          while q[top]<>k do begin inq[q[top]]:=false;belong[q[top]]:=tot;inc(hav[tot]);dec(top); end;

          dec(top);inq[k]:=false;belong[k]:=tot;inc(hav[tot]);

       end;

 end;

 procedure ins(u,v:longint);

 begin

    inc(cnt);c[cnt].t:=v;c[cnt].next:=a[u];a[u]:=cnt;inc(r[v]);

 end;

 begin

    assign(input,'semi.in');assign(output,'semi.out');reset(input);rewrite(output);

    readln(n,m,p);

    cnt:=;fillchar(last,sizeof(last),);

    for i:= to m do begin readln(u,v);add(u,v); end;

    fillchar(dfn,sizeof(dfn),);tot:=;

    for i:= to n do if dfn[i]= then begin cnt:=;top:=;tarjan(i); end;

    cnt:=;fillchar(a,sizeof(a),);fillchar(r,sizeof(r),);

    for i:= to n do

       begin

          j:=last[i];

          while j<> do

             begin

                if belong[i]<>belong[e[j].t] then ins(belong[i],belong[e[j].t]);

                j:=e[j].next;

             end;

       end;

    h:=;t:=;

    for i:= to tot do

       begin

          if r[i]= then begin inc(t);q[t]:=i; end;

          f[i]:=hav[i];g[i]:=;

       end;

    fillchar(vis,sizeof(vis),);

    while h<t do

       begin

          inc(h);i:=a[q[h]];

          while i<> do

             begin

                dec(r[c[i].t]);if r[c[i].t]= then begin inc(t);q[t]:=c[i].t; end;

                if vis[c[i].t]<>q[h] then

                   begin

                      if f[q[h]]+hav[c[i].t]>f[c[i].t] then begin f[c[i].t]:=f[q[h]]+hav[c[i].t];g[c[i].t]:=g[q[h]]; end

                      else if f[q[h]]+hav[c[i].t]=f[c[i].t] then g[c[i].t]:=(g[c[i].t]+g[q[h]]) mod p;

                      vis[c[i].t]:=q[h];

                   end;

                i:=c[i].next;

             end;

       end;

    max:=;

    for i:= to tot do if f[i]>max then begin max:=f[i];ans:=g[i]; end else if f[i]=max then ans:=(ans+g[i]) mod p;

    writeln(max);writeln(ans);

    close(input);close(output);

 end.

巴特西