题目大意

N个点的有向图中,定义“好点”为: 
从该点v出发可以到达的所有点u,均有一条路径使得u可达v。 
求出图中所有的“好点”,并按照顺序从小到大输出出来。

题目分析

图存在多个强连通分支,强连通分支内的所有点的行为可以视为一个点的行为:若强连通分支可以到达其他强连通分支,则该强连通分支内的所有点均可以到达其他分支;若强连通分支可以被其他点到达,则该强连通分支内的所有点均可以被其他点到达。因此,将图的强连通分支缩成一个点是一个经常会进行的操作。 
    将强连通分支缩成一个点之后,形成一个有向无环图。在有向无环图中,出度为0的点所代表的强连通分支,显然满足“好点”的要求;而出度不为0的点,显然存在它可以到达的点,但这些点不能到达它,故不满足“好点”的要求。因此,“好点”就是出度为0的点代表的强连通分支内的点。

实现(c++)

#include<stdio.h>
#include<string.h>
#include<vector>
#include<stack>
#include<set>
using namespace std;
#define MAX_NODE 5005
#define min(a, b) a < b? a:b
#define max(a, b) a > b? a:b vector<int> gGraph[MAX_NODE];
stack<int> 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<set<int> >gLinkFrom; //每个强连通分支,入点集合
vector<set<int> > 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<int> 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;
}

最新文章

  1. R中创建not-yet-evaluated对象
  2. Nginx模块开发-理解HTTP配置
  3. 1、Singleton 单件(创建模式)
  4. 在DataTable中添加行和列数据
  5. Two shortest
  6. cocos2d-x创建精灵动画
  7. Tomcat部署多个项目及相关配置
  8. 一个简单的基于canvas小游戏
  9. XML,Object,Json分析转换Xstream采用
  10. isPostBack原理
  11. 【Win 10 应用开发】UI Composition 札记(二):基本构件
  12. openstack的最简单安装
  13. OO第二次博客作业——电梯调度
  14. 招中高级web开发工程师
  15. JavaBean是什么,POJO是什么
  16. Github知识小结
  17. Java TreeSet的定制排序
  18. 生成式对抗网络GAN 的研究进展与展望
  19. npm私有仓库搭建
  20. 【mysql】排序方法

热门文章

  1. PKU OJ 1002 487-3279
  2. 解决javaWEB 下载文件中文名称乱码问题
  3. Apache HttpComponents 通过代理发送HTTP请求
  4. C++实现 找出10000以内的完数
  5. LINQ教程二:LINQ操作语法
  6. js学习笔记31----工厂方式
  7. 实现对DataGird控件的绑定操作
  8. JS三大经典变量命名法
  9. (转)非阻塞Connect对于select时应注意问题
  10. php Laravel 框架之建立后台目录