poj_2553 强连通分支&出度为0的点
2024-08-23 02:59:37
题目大意
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;
}
最新文章
- R中创建not-yet-evaluated对象
- Nginx模块开发-理解HTTP配置
- 1、Singleton 单件(创建模式)
- 在DataTable中添加行和列数据
- Two shortest
- cocos2d-x创建精灵动画
- Tomcat部署多个项目及相关配置
- 一个简单的基于canvas小游戏
- XML,Object,Json分析转换Xstream采用
- isPostBack原理
- 【Win 10 应用开发】UI Composition 札记(二):基本构件
- openstack的最简单安装
- OO第二次博客作业——电梯调度
- 招中高级web开发工程师
- JavaBean是什么,POJO是什么
- Github知识小结
- Java TreeSet的定制排序
- 生成式对抗网络GAN 的研究进展与展望
- npm私有仓库搭建
- 【mysql】排序方法