题目大意
有N个学校，这些学校之间用一些单向边连接，若学校A连接到学校B（B不一定连接到A），那么给学校A发一套软件，则学校B也可以获得。现给出学校之间的连接关系，求出至少给几个学校分发软件，才能使得所有的学校均可以获得软件；以及，至少需要添加几条单向边连接学校，才能使得给这些学校中任何一所发软件，其余的学校均可以收到。
题目分析
在一个图中，强连通分支内的任何一个点被“发软件”，则分支内的所有点均可以获得，因此首先求出强连通分支，将强连通分支合并为一点来看。 重构之后的图若只有一个点，则只需要向任何一所学校发送即可。即结果为1（至少向1所学校发布软件） 0（不需要添加新边来使得整个图连通）. 重构之后的图若有多个点，则考虑这些点中入度为0的点：入度为0的点不能被其他点到达，而一个入度不为0的点可以从某个入度为0的点到达，那么只需要向这些入度为0的点分发软件，就可以使得所有的点均能获得软件。 重构之后的图中有出度为0的点，在图中，入度为0的点（设为m个）无法从其他点到达，那么为了使得所有的点连通，需要m条路径连接到这m个入度为0的点；而出度为0的点（设为n个）无法到达其他点，那么为了使得所有的点连通，需要n条路径从这n个出度为0的点连出。于是，至少需要添加 max(m, n)条边，使得图中所有的点的入度和出度不为0. 同时，在一个有向无环图中，如果该图的所有点均可连接到一块，且每个点的出度和入度均不为0，则该图肯定强连通。于是，结果为 max(m,n)
实现(c++)
#include#include #include #include #include #define MAX_NODE 105#define min(a, b) a < b? a:b#define max(a, b) a > b? a:busing namespace std;vector > gGraph; //存储图结构stack gStack; //用于Tarjan算法bool gVisited[MAX_NODE]; //判断每个点是否被访问过bool gInStack[MAX_NODE]; //在Tarjan算法中判断点是否在栈中int gDfn[MAX_NODE]; //Tarjan算法中标记每个点最开始被访问的时间int gLow[MAX_NODE]; //Tarjan算法中标记从每个点开始的DFS过程中经过的点所能访问到的点的最小的开始时间int gClusterOfNode[MAX_NODE]; //标记每个点所在的强连通分支int gIndex; //标记点被第一次访问的时间int gClusterIndex; //强连通分支的编号//Tarjan算法求强连通分支void Tarjan(int u){ gLow[u] = gDfn[u] = ++gIndex; gVisited[u] = true; gInStack[u] = true; gStack.push(u); for (int i = 0; i < gGraph[u].size(); i++){ int v = gGraph[u][i]; if (!gVisited[v]){ Tarjan(v); gLow[u] = min(gLow[u], gLow[v]); } else if (gInStack[v]){ gLow[u] = min(gLow[u], gDfn[v]); } } if (gLow[u] == gDfn[u]){ int v; do{ v = gStack.top(); gStack.pop(); gInStack[v] = false; gClusterOfNode[v] = gClusterIndex; //标记所属的强连通分支编号 } while (v != u); gClusterIndex++; }}vector > gLinkTo; //将强连通分支缩成点之后，每个点所连接到的另外的点，用set 使得插入时不重复。用于统计出度vector > gLinkFrom; //将强连通分支缩成点之后，每个点被其他的点连接，用set 使得插入时不重复。用于统计入度//将强连通分支缩成点，然后统计每个强连通分支的入度和出度void ReconstructGraph(int nodes, int clusters){ gLinkTo.resize(clusters); gLinkFrom.resize(clusters); for (int u = 1; u <= nodes; u++){ for (int i = 0; i < gGraph[u].size(); i++){ int v = gGraph[u][i]; int uc = gClusterOfNode[u]; int vc = gClusterOfNode[v]; if (uc != vc){ //注意！！！自身不能连接到自身！ gLinkTo[uc].insert(vc); gLinkFrom[vc].insert(uc); } } }}int main(){ int n, u, v; scanf("%d", &n); gGraph.resize(n + 1); for (int i = 1; i <= n; i++){ while (scanf("%d", &v) && v != 0){ gGraph[i].push_back(v); } } gIndex = gClusterIndex = 0; memset(gVisited, false, sizeof(gVisited)); memset(gInStack, false, sizeof(gInStack)); for (int u = 1; u <= n; u++){ if (!gVisited[u]){ Tarjan(u); } } ReconstructGraph(n, gClusterIndex); int zero_outdegree = 0, zero_indegree = 0; for (int i = 0; i < gClusterIndex; i++){ if (gLinkFrom[i].empty()){ zero_indegree++; } if (gLinkTo[i].empty()){ zero_outdegree++; } } if (gClusterIndex == 1){ //如果只有一个强连通分支，则直接输出1 0 printf("1\n0\n"); }else //最少需要发送的版本个数，等于将强连通分支缩成点之后的图中 入度为0的点的个数， //因为，一个有向无环图中，所有入度不为0的点，一定可以从某个入度为0的点出发可达。 //而这些入度为0的点之间不能可达，故至少需要将所有这些入度为0的点设为起点 //需要连接多少条有向边才能使得整个图称为一个强连通图 //入度为0的点设为m个，不能被其他任何点可达，因此，要有 m条边连接到 这m个入度为0的点 //出度为0的点设为n个，无法到达其他点，因此要有n条边从这n个出度为0的点连接出去 //可以证明，在一个有向无环图中，所有点的入度和出度均不为0，则该图为强连通的 //则，至少有 max(m, n)条边。 printf("%d\n%d\n", zero_indegree, max(zero_outdegree, zero_indegree)); return 0;}