【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)。