本文共 1624 字,大约阅读时间需要 5 分钟。
题目大意:如果v点能够到的点,反过来能够到达v点,则称这个点为sink点,输出所有的sink点
RE
#include//https://blog.csdn.net/u014032715/article/details/25750911#include #include #include #define maxn 5020using 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 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