題目大意：如果v點能夠到的點，反過來能夠到達(dá)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;}//當(dāng)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; }

總結(jié)

以上是生活随笔為你收集整理的poj 2553 The Bottom of a Graph 未完的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。