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

 

——————————————————————————————————————————————

题目大意：

一个有向图，求图中的最大半连通子图的点数和方案数。

首先，对图进行缩点。因为环内的点肯定是连通的。

然后，图就变成了有向无环图，这样在上面进行拓扑排序。

最后，在拓扑序上进行DP。

只得了40分，后来看别的程序才发现问题，注意去重边。

——————————————————————————————————————————————

1 #include
       
         2 using namespace std; 3 const int maxn=1e5+10,maxm=1e6+10; 4 struct edge 5 { 6     int u,v,nxt; 7 }e[maxm],ee[maxm]; 8 int head[maxn],js,headd[maxn],jss; 9 void addage(edge e[],int head[],int &js,int u,int v)10 {11     e[++js].u=u;e[js].v=v;12     e[js].nxt=head[u];head[u]=js;13 }14 int dfn[maxn],low[maxn],cnt,st[maxn],top,lt[maxn],lts,ltn[maxn];15 void  tarjan(int u)16 { 17     dfn[u]=low[u]=++cnt;18     st[++top]=u;19     for(int i=head[u];i;i=e[i].nxt)20     {21         int v=e[i].v;22         if(!dfn[v])23         {24             tarjan(v);25             low[u]=min(low[u],low[v]);26         }27         else if(!lt[v])28             low[u]=min(low[u],dfn[v]);29     }30     if(dfn[u]==low[u])31     {32         lt[u]=++lts;ltn[lts]++;33         while(st[top]!=u)lt[st[top--]]=lts,ltn[lts]++;34         --top;35     }36 }37 int n,m,x;38 int f[maxn],ff[maxn];39 int cd[maxn],rd[maxn];40 int maxd,maxf;41 int pc[maxn];42 queue
        
         q;43 void dfs()44 {45     while(!q.empty())46     {47         int u=q.front();q.pop();48         maxd=max(maxd,f[u]);49         for(int i=headd[u];i;i=ee[i].nxt)50         {51             int v=ee[i].v;52             rd[v]--;53             if(rd[v]==0)q.push(v);54             if(pc[v]==u)continue;55             if(f[u]+ltn[v]>f[v])56             {57                 f[v]=f[u]+ltn[v];58                 ff[v]=ff[u];59                 60             }61             else if(f[u]+ltn[v]==f[v])62             {63                 ff[v]=(ff[u]+ff[v])%x;64             }65             pc[v]=u;66         }67     }68 }69 int main()70 {71     scanf("%d%d%d",&n,&m,&x);72     for(int u,v,i=1;i<=m;++i)73     {74         scanf("%d%d",&u,&v);75         addage(e,head,js,u,v);76     }77     for(int i=1;i<=n;++i)78         if(!dfn[i])tarjan(i);79     for(int u=1;u<=n;++u)80         for(int i=head[u];i;i=e[i].nxt)81             if(lt[e[i].u]!=lt[e[i].v])addage(ee,headd,jss,lt[e[i].u],lt[e[i].v]),cd[lt[e[i].u]]++,rd[lt[e[i].v]]++;82     for(int i=1;i<=lts;++i)83         if(rd[i]==0)q.push(i),f[i]=ltn[i],ff[i]=1;84     dfs();85     for(int i=1;i<=lts;++i)86     {87         if(f[i]==maxd)maxf=(maxf+ff[i])%x;88     }89     printf("%d\n%d\n",maxd,maxf);90     return 0;91 }