题目大意:n个点m条有向边的图,一条路径上最多有多少个点?
题目描述
一个旅游胜地,有n个景点和m条有向道路,你可以从任意一个景点出发,沿着有向道路走下去,最多可以经过多少个景点?
输入
第一行:两个整数n和m
接下来m行,每行2个整数a和b,表示a到b有一条有向道路。
输出
输出一个整数,表示最多可以逛的景点数量。
样例输入
5 6
1 2
2 3
1 4
4 1
2 5
5 3
样例输出
5
提示
n不超过10万,m不超过n的3倍,n在10个点的数据范围:5, 10, 100, 500, 1000, 5000, 10000, 30000, 50000, 70000, 100000
解题思路
如果图中没有环,那么就是一个有向无环图(DAG),可以用动态规划的思想推出每个点可以到达的景点数量。如果有环的话,就比较麻烦,因为你不知道从哪个点出发,而且不清楚环中有多少个点。如果可以把环看成一个点,那就没问题了。这就需要用到缩点。
先介绍几个概念:强连通,有向图中的两个点能够互相到达,那么他们强连通;强连通图,有向图中任意两点能够互相到达,那么这个图就是强连通图;强连通分量,有向图中的极大强连通图子图就是强连通分量。对于这道题,我们需要把强连通分量看成一个点,因为强连通分量中的点可以互相到达,选任意一个点出发,结果是一样的。那么,怎么求强连通分量呢?
用深度优先搜索,点的状态分为3种——没访问过(0)、访问中(+)、访问完(-)。如果一个搜索中的点,搜到一个也是搜索中的点,那么他们可以互相到达,属于同一个强连通分量。我们可以用并查集来合并、记录该强连通分量缩成的点。一开始每个点都可以看作一个强连通子图,他们缩成的点就是自己本身,即f[i]=i。搜索的过程中,如果下一个点没访问过,就一直搜索下去;如果遇到访问完的点,就不需要走下去了,因为下面已经走过了;如果遇到一个访问中的点,就需要用并查集合并他们。合并的时候需要注意,要选择深度小的点作为公共祖先,这样才能保证这个强连通分量访问的状态正确。如果选了一个深度大的,那么深度大的点搜索完了,强连通分量就提前搜索完、不能再扩大了!
统计强连通分量个数:看一下各个点的祖先,不同祖先的个数就是强连通分量的个数。
输出强连通分量:祖先相同的结点一起输出。
缩点:原来的边,每个点都改成祖先结点,重新建边,建边过程中,如果发现是同一个点,即同一个强连通分量,就可以省去这条边了。