OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【ZJOI2007】最大半连通子图

【题目描述】

一个有向图称为半连通的(Semi-Connected),如果满足: 

对于图中任意两点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的余数。

【输入】

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

【输出】

包含两行,第一行包含一个整数K。第二行包含整数C Mod X。

【输入样例】

6 6 20070603
1 2
2 1
1 3
2 4
5 6
6 4

【输出样例】

3

3

【数据范围】

对于20%的数据,N≤18;

对于60%的数据,N≤10000; 

对于100%的数据,N≤100000,M≤1000000;

对于100%的数据,X≤10^8.

【题解】

首先考虑u和v相互连通,即u和v属于同一强连通分量的情况,这是满足条件的,所以先缩点,构建新图。现在新图中是不含可以相互连通的点了,因此要找单向连通,即一条点权和最长链,然后统计最长链条数就能得到答案了。

注意题目中说“E´是E中所有跟V´有关的边”,重新构图时会出现跨过两个强连通分量的重边,这些边是要舍弃的。

【代码】

查错查了半天……下次要记得边算边取模……

http://paste.ubuntu.com/8647479/

评论

© OI技术宅 | Powered by LOFTER