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

HINT

Source

 

第一遍做时 思路还是比较正确

先tarjan缩点 再建新图 从入度为0的点跑 bfs 求最长链及条数 

但是只有30分 因为我建完新图没有判重边 还有不知名的MLE和TLE (我也很绝望啊)

后来才知道 这个新图内不能有重边 

于是就 判重之后就拓扑排序 统计在这个点的半连通子图的点数和个数

 

1 #include 
      
         2 #include 
       
          3 #include 
        
           4   5 const int MAXN=100010;  6   7 int n,m,mod,id,inr,top,ans,total;  8   9 int dfn[MAXN],low[MAXN],stack[MAXN],belong[MAXN],siz[MAXN],in[MAXN]; 10  11 int f[MAXN][2]; 12  13 bool vis[MAXN]; 14  15 struct node { 16     int to; 17     int next; 18     node() {} 19     node(int to,int next):to(to),next(next) {} 20 }; 21 node e[MAXN*10],r[MAXN*10]; 22  23 int head[MAXN],tot,Head[MAXN],tal; 24  25 inline void read(int&x) { 26     int f=1;register char c=getchar(); 27     for(x=0;!isdigit(c);c=='-'&&(f=-1),c=getchar()); 28     for(;isdigit(c);x=x*10+c-48,c=getchar()); 29     x=x*f; 30 } 31  32 inline void add(int x,int y) { 33     e[++tot]=node(y,head[x]); 34     head[x]=tot; 35 } 36  37 inline int min(int a,int b) {return a
         

q; 89 for(int i=1;i<=id;++i) { 90 f[i][0]=siz[i];f[i][1]=1; 91 if(!in[i]) q.push(i); 92 } 93 while(!q.empty()) { 94 int u=q.front();; 95 q.pop(); 96 for(int i=Head[u];i;i=r[i].next) { 97 int v=r[i].to; 98 --in[v]; 99 if(!in[v]) q.push(v);100 if(f[v][0]

ans) ans=f[i][0],total=f[i][1];106 else if(f[i][0]==ans) total+=f[i][1],total%=mod;107 }108 printf("%d\n%d\n",ans,total);109 return 0;110 }111 112 int sb=hh();113 int main (int argc,char**argv) {;}