http://poj.org/problem?id=2553
sink中的点v如果能到w点，那么w点也必须能到v点，所以是所有出度为0的连通分量的点。
缩点后把所有的出度为0的点放到数组里sort后输出就好啦
#include<iostream> #include<vector> #include<queue> #include<stack> #include<cstring> #include<cmath> #include<map> #include<set> #include<cstdio> #include<algorithm> #define debug(a) cout<<#a<<"="<<a<<endl; using namespace std; const int maxn=5e3+200; typedef long long LL; vector<LL>g[maxn]; stack<LL>s; bool instack[maxn]; LL dfn[maxn],low[maxn],times=0,cnt=0,col[maxn],outdu[maxn]; LL shuchu[maxn]; vector<LL>num[maxn]; void init() { times=cnt=0; for(LL i=0;i<maxn;i++) num[i].clear(),g[i].clear(); memset(low,0,sizeof(low)); memset(dfn,0,sizeof(dfn)); memset(col,0,sizeof(col)); memset(outdu,0,sizeof(outdu)); memset(shuchu,0,sizeof(shuchu)); } void tarjan(LL x) { dfn[x]=low[x]=++times; s.push(x);instack[x]=true; for(LL i=0;i<g[x].size();i++){ LL to=g[x][i]; if(!dfn[to]){ tarjan(to); low[x]=min(low[x],low[to]); } else if(instack[to]) low[x]=min(low[x],dfn[to]); } if(dfn[x]==low[x]){ cnt++; LL y; do{ y=s.top(); col[y]=cnt; num[cnt].push_back(y); instack[y]=false; s.pop(); }while(y!=x); return ; } } int main(void) { cin.tie(0);std::ios::sync_with_stdio(false); LL n,m; while(cin>>n&&n) { cin>>m; init(); for(LL i=1;i<=m;i++){ LL x,y;cin>>x>>y; g[x].push_back(y); } for(LL i=1;i<=n;i++){ if(!dfn[i]) tarjan(i); } for(LL i=1;i<=n;i++){ for(LL j=0;j<g[i].size();j++){ if(col[i]!=col[g[i][j]]){ outdu[col[i]]++; } } } LL ans=0; for(LL i=1;i<=cnt;i++){ if(outdu[i]==0){ for(LL j=0;j<num[i].size();j++){ shuchu[++ans]=num[i][j]; } } } sort(shuchu+1,shuchu+ans+1); for(LL i=1;i<=ans;i++) cout<<shuchu[i]<<" "; cout<<endl; } return 0; }
