首先缩点

然后半连通其实就是缩点后节点数最多的链

注意这里一定是一条链才一定是半连通

然后重建图拓扑排序上做dp即可

1 type node=record  2        po,next:longint;  3      end;  4   5 var w,e:array[0..1000010] of node;  6     rd,be,c,f,g,p,q,st,dfn,low:array[0..100010] of longint;  7     v:array[0..100010] of boolean;  8     s,mo,i,n,m,x,y,j,h,t,ans1,ans2,len:longint;  9  10 function min(a,b:longint):longint; 11   begin 12     if a>b then exit(b) else exit(a); 13   end; 14  15 procedure fadd(x,y:longint); 16   begin 17     inc(len); 18     w[len].po:=y; 19     w[len].next:=q[x]; 20     q[x]:=len; 21   end; 22  23 procedure add(x,y:longint); 24   begin 25     inc(len); 26     e[len].po:=y; 27     e[len].next:=p[x]; 28     p[x]:=len; 29   end; 30  31 procedure tarjan(x:longint); 32   var i,y:longint; 33   begin 34     inc(h); 35     dfn[x]:=h; 36     low[x]:=h; 37     inc(t); 38     st[t]:=x; 39     v[x]:=true; 40     i:=p[x]; 41     while i<>0 do 42     begin 43       y:=e[i].po; 44       if dfn[y]=0 then 45       begin 46         tarjan(y); 47         low[x]:=min(low[x],low[y]); 48       end 49       else if v[y] then low[x]:=min(low[x],low[y]); 50       i:=e[i].next; 51     end; 52     if dfn[x]=low[x] then 53     begin 54       inc(s); 55       while st[t+1]<>x do 56       begin 57         y:=st[t]; 58         v[y]:=false; 59         inc(c[s]); 60         be[y]:=s; 61         dec(t); 62       end; 63     end; 64   end; 65  66 begin 67   readln(n,m,mo); 68   for i:=1 to m do 69   begin 70     readln(x,y); 71     add(x,y); 72   end; 73   for i:=1 to n do 74     if dfn[i]=0 then 75     begin 76       h:=0; 77       t:=0; 78       tarjan(i); 79     end; 80  81   len:=0; 82   for i:=1 to n do 83   begin 84     j:=p[i]; 85     while j<>0 do 86     begin 87       y:=e[j].po; 88       if be[y]<>be[i] then 89       begin 90         fadd(be[i],be[y]); 91         inc(rd[be[y]]); 92       end; 93       j:=e[j].next; 94     end; 95   end; 96   t:=0; 97   for i:=1 to s do 98     if rd[i]=0 then 99     begin100       inc(t);101       st[t]:=i;102       f[i]:=c[i];103       g[i]:=1;104     end;105   h:=1;106   fillchar(low,sizeof(low),0);107   while h<=t do108   begin109     x:=st[h];110     i:=q[x];111     while i<>0 do112     begin113       y:=w[i].po;114       dec(rd[y]);115       if rd[y]=0 then116       begin117         inc(t);118         st[t]:=y;119       end;120       if low[y]<>x then121       begin122         low[y]:=x;123         if f[y]
      
       ans1 then138     begin139       ans1:=f[i];140       ans2:=g[i];141     end142     else if f[i]=ans1 then ans2:=(ans2+g[i]) mod mo;143   writeln(ans1);144   writeln(ans2);145 end.