C++,给定一张n个点m条边的有向图,统计有多少点满足:从图上任意点出发,都可以沿图上的有向边到达这个点
时间: 2023-02-25 17:11:33 浏览: 182
称这样的点为"强连通点",要统计这样的点的个数,就需要使用图的强连通分量的概念。强连通分量指的是一个点集,其中任意两点都是强连通的,也就是说可以从任意一个点出发到达其他任意点。强连通分量的点的个数就是答案。
C 语言中,可以使用 tarjan 算法或者 kosaraju 算法来求解图的强连通分量。具体实现细节可以参考一些数据结构与算法的学习资料。
阅读全文