分类： C/C++
2010-05-06 23:25:21
题意：
网络中有一些学校，每个学校可以分发软件给其他学校。可以向哪个分发取决于他们各自维护的一个清单。
有两个问题，1：至少要copy多少份新软件给那些学校， 才能使得每个学校都能得到。
2:要在所有的学校的清单里面至少一共增加几项才能 使得 把软件给任意一个学校，所有的学校都能收得到。
思路：
整个就是一个有向图啊， 学校是节点， 它的表里面有从他出发到其他节点的边。
问题一： 要使每个学校都能收到，就是计算图里面一共有多少入度是0的点，这个好理解。
问题二： 先学习下计算强连通分支的算法——kosaraju, 用两次dij的， 然后缩点，把每一块看成一个点，出来一个新的有向图。然后计算出度为0的入度为0的点各有多少， 大的那个就是答案。至于为什么， 还没搞明白。
做的时候用邻接表建两个图，kosaraju算法用到两次dfs， 第二次的时候，d[i]记录vi点在哪个连通分支里面，返回后， 枚举每个顶点统计每个分支的入度和出度， 为0的各有多少， 输出大的。
值得注意的是， 当只有一个强连通分支的时候，就是缩点后只有一个点，虽然入度出度为0的都有一个，但是实际上不需要增加清单的项了，所以答案是1，0
