首页 > 代码库 > The Bottom of a Graph
The Bottom of a Graph
poj——The Bottom of a Graph
Time Limit: 3000MS | Memory Limit: 65536K | |
Total Submissions: 11044 | Accepted: 4542 |
Description
We will use the following (standard) definitions from graph theory. Let V be a nonempty and finite set, its elements being called vertices (or nodes). Let E be a subset of the Cartesian product V×V, its elements being called edges. ThenG=(V,E) is called a directed graph.
Let n be a positive integer, and let p=(e1,...,en) be a sequence of length n of edges ei∈E such that ei=(vi,vi+1) for a sequence of vertices (v1,...,vn+1). Then p is called a path from vertex v1 to vertex vn+1 in G and we say that vn+1is reachable from v1, writing (v1→vn+1).
Here are some new definitions. A node v in a graph G=(V,E) is called a sink, if for every node w in G that is reachable from v, v is also reachable from w. The bottom of a graph is the subset of all nodes that are sinks, i.e.,bottom(G)={v∈V|∀w∈V:(v→w)⇒(w→v)}. You have to calculate the bottom of certain graphs.
Let n be a positive integer, and let p=(e1,...,en) be a sequence of length n of edges ei∈E such that ei=(vi,vi+1) for a sequence of vertices (v1,...,vn+1). Then p is called a path from vertex v1 to vertex vn+1 in G and we say that vn+1is reachable from v1, writing (v1→vn+1).
Here are some new definitions. A node v in a graph G=(V,E) is called a sink, if for every node w in G that is reachable from v, v is also reachable from w. The bottom of a graph is the subset of all nodes that are sinks, i.e.,bottom(G)={v∈V|∀w∈V:(v→w)⇒(w→v)}. You have to calculate the bottom of certain graphs.
Input
The input contains several test cases, each of which corresponds to a directed graph G. Each test case starts with an integer number v, denoting the number of vertices of G=(V,E), where the vertices will be identified by the integer numbers in the set V={1,...,v}. You may assume that 1<=v<=5000. That is followed by a non-negative integer e and, thereafter, e pairs of vertex identifiers v1,w1,...,ve,we with the meaning that (vi,wi)∈E. There are no edges other than specified by these pairs. The last test case is followed by a zero.
Output
For each test case output the bottom of the specified graph on a single line. To this end, print the numbers of all nodes that are sinks in sorted order separated by a single space character. If the bottom is empty, print an empty line.
Sample Input
3 31 3 2 3 3 12 11 20
Sample Output
1 32
Source
Ulm Local 2003
定义:点v是汇点须满足 --- 对图中任意点u,若v可以到达u则必有u到v的路径;若v不可以到达u,则u到v的路径可有可无。
题目大意:
如果v点能够到的点,反过来能够到达v点,则称这个点为sink点,输出所有的sink点
思路:
我们这样想:对于一对点如果他们能够相互到达,那么他们在缩点是一定能缩成一个点,这样我们剩下的就是不能缩点的情况了。
也就是说我们缩完点后就剩下两种情况:1.这个点连向其它的点但是那个点不连向他 2.这个点不连向任意点
在这两种情况中第二种情况对于sink点的要求是显然成立的。而第一种情况是不成立的,因为这种情况一定是另一个点不连向这个点的,也就是说她是单向的。
(最开始没明白的地方。。。)
我们为何要在判断一个点的出度为0时循环到n??
因为我们把这些点缩成一个点,这样我们在进行判断每一个点的时候有两种选择:
1.我们先将出度为零的强连通分量记录在一个数组中。然后再用一个双重循环来判断一下那个点在这个数组中
2.我们用一个一重循环,循环到n,判断这个点所属的强连通分量缩点后对应的点的出度是否为0,若是0,用一个数组将其储存下来。
排序
输出这个数组内的元素
代码:
#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>#define N 10000using namespace std;bool vis[N];int n,m,x,y,sum,tim,tot,top;int out[N],dfn[N],low[N],ans[N],head[N],stack[N],belong[N],point[N];inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘) {if(ch==‘-‘) f=-1;ch=getchar();} while(ch<=‘9‘&&ch>=‘0‘) {x=x*10+ch-‘0‘;ch=getchar();} return f*x;}struct Edge{ int from,to,next; }edge[500010];void add(int x,int y){ tot++; edge[tot].to=y; edge[tot].next=head[x]; head[x]=tot;} void begin(){ tot=0;top=0;sum=0,tim=0; memset(edge,0,sizeof(edge)); memset(stack,0,sizeof(stack)); memset(head,0,sizeof(head)); memset(out,0,sizeof(out)); memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(belong,0,sizeof(belong)); memset(ans,0,sizeof(ans));}int tarjan(int now){ dfn[now]=low[now]=++tim; stack[++top]=now;vis[now]=true; for(int i=head[now];i;i=edge[i].next) { int t=edge[i].to; if(vis[t]) low[now]=min(low[now],dfn[t]); else if(!dfn[t]) tarjan(t),low[now]=min(low[now],low[t]); } if(dfn[now]==low[now]) { sum++;belong[now]=sum; for(;stack[top]!=now;top--) { vis[stack[top]]=false; belong[stack[top]]=sum; } vis[now]=false;top--; } } void shrink_point(){ for(int i=1;i<=n;i++) for(int j=head[i];j;j=edge[j].next) if(belong[i]!=belong[edge[j].to]) out[belong[i]]++;}int main(){ while(~scanf("%d",&n)&&n) { m=read();begin(); for(int i=1;i<=m;i++) x=read(),y=read(),add(x,y); for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i); shrink_point(); x=0; for(int i=1;i<=n;i++) if(!out[belong[i]]) ans[++x]=i; sort(ans+1,ans+1+x); if(x) { for(int i=1;i<x;i++) printf("%d ",ans[i]); printf("%d\n",ans[x]); } else printf("\n"); } return 0; }
注意:注意数组的大小!!
The Bottom of a Graph
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。