「BZOJ1093」[ZJOI2007] 最大半连通子图

2014年10月8日7,1652

Description

Input

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

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

对于100%的数据, N ≤100000, M ≤1000000;对于100%的数据, X ≤10^8。

题解

 缩点。。。然后用拓扑排序找最长链。。
注意缩点后连通块间重边要处理下

 

 

avatar
1 Comment threads
1 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
2333 Recent comment authors
  Subscribe  
提醒
2333
2333

vis数组有什么作用?

2333
2333

重边。。