本文主要是介绍poj 2553 The Bottom of a Graph 未完，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目大意：如果v点能够到的点，反过来能够到达v点，则称这个点为sink点，输出所有的sink点
RE
#include <iostream>//https://blog.csdn.net/u014032715/article/details/25750911
#include <stack>
#include <cstdio>
#include <cstring>
#define maxn 5020
using namespace std;
//void init();
int low[maxn];
int dfn[maxn];
bool vis[maxn];
int first[maxn],b[maxn],c[maxn];
struct node
{int to,next;
}edge[maxn+3000];
int index,in;
int n,m,ans;
stack<int>s;
void add(int a,int b)
{edge[index].to=b;edge[index].next=first[a];first[a]=index++;
}
void init()
{index=1;in=0;ans=0;memset(first,0,sizeof(first));memset(vis,0,sizeof(vis));memset(low,0,sizeof(low));//memset(dfn,0,sizeof(dfn));memset(b,0,sizeof(b));memset(c,0,sizeof(c));memset(edge,0,sizeof(edge));
}
void trajan(int u)
{low[u]=dfn[u]=in++;s.push(u);vis[u]=1;for(int i=first[u];i;i=edge[i].next){int k=edge[i].to;if(dfn[k]==0){trajan(k);if(low[u]>low[k])low[u]=low[k];}else if(vis[k]){if(low[u]>low[k])low[u]=low[k];}}if(low[u]==dfn[u]){/* while(!s.empty()&&s.top()!=u){int q=s.top();b[q]=ans;vis[q]=0;s.pop();}b[s.top()]=ans;vis[s.top()]=0;s.pop();*/int t;do{t=s.top();vis[t]=0;b[t]=ans;s.pop();}while(!s.empty()&&t!=u);ans++;}
}
int main()
{int aa,bb;while(cin>>n,n){cin>>m;init();for(int i=0;i<m;++i){scanf("%d%d",&aa,&bb);add(aa,bb);}for(int j=1;j<=n;++j)if(dfn[j]==0)trajan(j);for(int i=1;i<=n;++i){for(int j=first[i];j;j=edge[j].next){int p=edge[j].to;if(b[i]!=b[p])//i和p所在图不是一个。{c[b[i]]++;//break;}//当c[b[i]]=0时，代表i所在的顶点可以与其他点形成sink点}}int tag=1;for(int i=1;i<=n;++i){if(c[b[i]]==0){if(tag){cout<<i;tag=0;}elsecout<<' '<<i;}}cout<<endl;}return 0;
}这篇关于poj 2553 The Bottom of a Graph 未完的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
