首页 > 代码库 > The Bottom of a Graph

The Bottom of a Graph

2024-10-08 07:22:02   219人阅读

　　　　　　　　　　　　　                                　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.

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


联系
我们