题目大意
N个点的有向图中，定义“好点”为： 从该点v出发可以到达的所有点u，均有一条路径使得u可达v。 求出图中所有的“好点”，并按照顺序从小到大输出出来。
题目分析
图存在多个强连通分支，强连通分支内的所有点的行为可以视为一个点的行为：若强连通分支可以到达其他强连通分支，则该强连通分支内的所有点均可以到达其他分支；若强连通分支可以被其他点到达，则该强连通分支内的所有点均可以被其他点到达。因此，将图的强连通分支缩成一个点是一个经常会进行的操作。 将强连通分支缩成一个点之后，形成一个有向无环图。在有向无环图中，出度为0的点所代表的强连通分支，显然满足“好点”的要求；而出度不为0的点，显然存在它可以到达的点，但这些点不能到达它，故不满足“好点”的要求。因此，“好点”就是出度为0的点代表的强连通分支内的点。
实现(c++)
#include#include #include #include #include using namespace std;#define MAX_NODE 5005#define min(a, b) a < b? a:b#define max(a, b) a > b? a:bvector gGraph[MAX_NODE];stack gStack;int gDfn[MAX_NODE];int gLow[MAX_NODE];bool gVisited[MAX_NODE];bool gInStack[MAX_NODE];int gClusterOfNode[MAX_NODE];int gIndex;int gClusterIndex;//Tarjan算法求强连通分支void Tarjan(int u){ gDfn[u] = gLow[u] = ++gIndex; gInStack[u] = true; gVisited[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 (gDfn[u] == gLow[u]){ int v; do{ v = gStack.top(); gStack.pop(); gInStack[v] = false; gClusterOfNode[v] = gClusterIndex; } while (v != u); ++gClusterIndex; }}vector >gLinkFrom; //每个强连通分支，入点集合 vector > gLinkTo; //每个强连通分支，出点集合void ReconstructGraph(int nodes, int clusters){ gLinkFrom.clear(); gLinkFrom.resize(clusters); gLinkTo.clear(); gLinkTo.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, r; while (scanf("%d", &n) && n != 0){ scanf("%d", &r); for (int i = 0; i <= n; i++){ gGraph[i].clear(); } int u, v; for (int i = 0; i < r; i++){ scanf("%d %d", &u, &v); gGraph[u].push_back(v); } memset(gVisited, false, sizeof(gVisited)); memset(gInStack, false, sizeof(gInStack)); gIndex = gClusterIndex = 0; for (int i = 1; i <= n; i++){ if (!gVisited[i]) Tarjan(i); } ReconstructGraph(n, gClusterIndex); //将染色后的图进行重构（即设置强连通分支） set zero_outdegree_cluster_id; //出度为0的强连通分支的集合 for (int i = 0; i < gClusterIndex; i++){ if (gLinkTo[i].empty()){ //出度为0，强连通分支 zero_outdegree_cluster_id.insert(i); } } //遍历每个点，判断其是否属于那些出度为0的强连通分支 for (int u = 1; u <= n; u++){ if (zero_outdegree_cluster_id.find(gClusterOfNode[u]) != zero_outdegree_cluster_id.end()){ printf("%d ", u); } } printf("\n"); } return 0;}