【POJ 1236 Network of Schools】强联通分量问题 Tarjan算法，缩点
- 时间:
- 浏览:0
求SCC每项参考了 http://blog.csdn.net/dgq8211/article/details/7834292
TaskB: 大约增加几个边，就能都可不里能使得，发软件给任一学校，所有学校都能都可不里能收到。
缩点的做法很暴力，将每个强联通分量重新编号为另另兩个多多集合，在求SCC时记录belong。
TaskA: 大约收集给几个学校，就能都可不里能使所有的学校都能得到软件。
现要求解另另兩个多多问题报告 ：
题目链接：http://poj.org/problem?id=1236
题意：给定另另兩个多多表示n所学校网络连通关系的有向图。现要通过网络收集软件，规则是：若顶点u,v居于通路，发给u，则v能都可不里能通过网络从u接收到。
思路：先进行强联通分量分解，就让缩点，并计算缩点后每个点的出度、入度。入度为0的点的总数为 a ，出度为0的点总数为 b。a即TaskA的答案，而TaskB的答案为max(a, b)。