【bzoj1093】[ZJOI2007]最大半连通子图

2014年10月8日2,8492

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。

题解

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

 

 

  • 23332016年1月7日 下午2:06 回复

    vis数组有什么作用?

    #1  
    • 23332016年1月7日 下午2:10 回复

      重边。。

      #11