[poj 2553]The Bottom of a Graph[Tarjan强连通分量]

发布时间:2016-12-9 2:40:02 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"[poj 2553]The Bottom of a Graph[Tarjan强连通分量]",主要涉及到[poj 2553]The Bottom of a Graph[Tarjan强连通分量]方面的内容,对于[poj 2553]The Bottom of a Graph[Tarjan强连通分量]感兴趣的同学可以参考一下。

题意: 求出度为0的强连通分量. 思路: 缩点 具体有两种实现: 1.遍历所有边, 边的两端点不在同一强连通分量的话, 将出发点所在强连通分量出度+1. #include <cstdio> #include <cstring> #include <stack> #include <algorithm> using namespace std; //0.03s 4856K const int MAXN = 5005; struct Pool { int pre, v; }p[MAXN*100];//适当开 int num,head[MAXN]; int low[MAXN]; int dfn[MAXN],Index; int id[MAXN],size; bool vis[MAXN]; stack<int> s; int n,m; int deg[MAXN]; void clear() { num = 1;//求邻边,异或方便,从2开始 memset(head,0,sizeof(head)); memset(vis,false,sizeof(vis)); memset(low,0,sizeof(low)); memset(dfn,0,sizeof(dfn)); memset(deg,0,sizeof(deg)); Index = size = 0; while(!s.empty()) s.pop(); } void add(int u, int v) { p[++num].v = v; p[num].pre = head[u];//pre为0,说明该边为第一条边 head[u] = num; } void Tarjan(int u) { dfn[u] = low[u] = ++Index; s.push(u); vis[u] = true; for(int tmp = head[u],k;k = p[tmp].v,tmp; tmp = p[tmp].pre) { if(!dfn[k]) { Tarjan(k); low[u] = min(low[u], low[k]); } else if(vis[k]) { low[u] = min(low[u], low[k]); ///low[u] = min(low[u], dfn[k]);这两种都可以啦~ } } if(dfn[u]==low[u]) { size++; int k; do { k = s.top(); s.pop(); vis[k] = false; id[k] = size; }while(k!=u); } } void cal() { for(int i=1;i<=n;i++) { for(int tmp = head[i],k;k = p[tmp].v,tmp; tmp = p[tmp].pre) { if(id[i]!=id[k]) { deg[id[i]]++; } } } } int main() { while(scanf("%d",&n),n) { clear(); scanf("%d",&m); for(int i=0,u,v;i<m;i++) { scanf("%d %d",&u,&v); add(u,v); } for(int i=1;i<=n;i++) { if(!dfn[i]) Tarjan(i); } cal(); bool blank = false; for(int i=1;i<=n;i++) { if(!deg[id[i]]) { if(!blank) { printf("%d",i); blank = true; } else printf(" %d",i); } } printf("\n"); } } 2. 在dfs的过程中,标记出度. 设当前节点为u 若访问到了黑色点, 则出度不为0. 若访问到了灰色点, 正常 若访问到了白色点, 则这个白色点k 若被搜索之后属于同一强连通分量,则low[ k ] < dfn[ k ] (注意,并不一定有 low[ k ] < low[ u ], 因为k可能连接到了较靠后的灰色点,而u之前已经被较靠前的灰色点更新过). 若被搜索之后属于另一个(不同于u的)强连通分量, 那么可以证明 low[ k ] == dfn[ k ], 即k一定是入口. 黑体字的两条就包括了所有出度非0的情况. 据此来实现缩点. #include <cstdio> #include <cstring> #include <stack> #include <algorithm> using namespace std; //0.03s 4812K const int MAXN = 5005; struct Pool { int pre, v; }p[MAXN*100];//适当开 int num,head[MAXN]; int low[MAXN]; int dfn[MAXN],Index; int id[MAXN],size; bool vis[MAXN]; stack<int> s; int n,m; bool black[MAXN]; bool odd[MAXN]; void clear() { num = 1; memset(head,0,sizeof(head)); memset(vis,false,sizeof(vis)); memset(low,0,sizeof(low)); memset(dfn,0,sizeof(dfn)); memset(black,false,sizeof(black)); memset(odd,false,sizeof(odd)); Index = size = 0; while(!s.empty()) s.pop(); } void add(int u, int v) { p[++num].v = v; p[num].pre = head[u]; head[u] = num; } void Tarjan(int u) { dfn[u] = low[u] = ++Index; s.push(u); vis[u] = true; for(int tmp = head[u],k;k = p[tmp].v,tmp; tmp = p[tmp].pre) { if(!dfn[k]) { Tarjan(k); if(low[k]==dfn[k])///如果访问到了白色点,那么新的强连通分量的入口一定在这个点 black[u] = true; low[u] = min(low[u], low[k]); } else if(vis[k]) { low[u] = min(low[u], low[k]); } else black[u] = true; }///low只是指"当前找到的强连通分量的进入时间戳" ///而非"极大强连通分量"的进入时间戳.但是肯定小于自己的时间戳(恰好是进入点的话就是等于). if(dfn[u]==low[u]) { size++; int k; do { k = s.top(); s.pop(); vis[k] = false; id[k] = size; if(black[k]) odd[size] = true; }while(k!=u); } } int main() { while(scanf("%d",&n),n) { clear(); scanf("%d",&m); for(int i=0,u,v;i<m;i++) { scanf("%d %d",&u,&v); add(u,v); } for(int i=1;i<=n;i++) { if(!dfn[i]) Tarjan(i); } bool blank = false; for(int i=1;i<=n;i++) { if(!odd[id[i]]) { if(!blank) { printf("%d",i); blank = true; } else printf(" %d",i); } } printf("\n"); } }

上一篇:奇异值分解在机器视觉中的应用
下一篇:【分享】PK10彩票历史数据

相关文章

相关评论