解题思路：用tarjan求强连通分量，缩图为G’，map[id[i]]==0,id[i]表示节点i的新节点，map[]==0说明新节点的出度为0，则i即为所求的节点，the bottom of the graph
#include<iostream> using namespace std; #include<cstdlib> #define N 5005 typedef struct node* pointer; struct node { int ver; pointer next; }; pointer g[N]; pointer r[N]; int low[N],ord[N],stk[N],scnt,cnt,result[N],id[N]; bool instk[N],map[N]; int cmp(const void *a,const void *b) { return *(int *)a-*(int *)b; } void insert(int u,int v,pointer *G) { pointer ptr=new node; ptr->ver=v; ptr->next=G[u]; G[u]=ptr; } void tarjan(int e) { int t; pointer ptr; low[e]=++cnt; ord[e]=cnt; stk[++stk[0]]=e; instk[e]=true; ptr=g[e]; while(ptr!=NULL) { t=ptr->ver; if(!ord[t]) { tarjan(t); if(low[e]>low[t]) low[e]=low[t]; } if(instk[t]&&low[e]>ord[t]) low[e]=ord[t]; ptr=ptr->next; } if(low[e]==ord[e]) { scnt++; do { t=stk[stk[0]--]; insert(scnt,t,r); id[t]=scnt; instk[t]=false; }while(t!=e); } } void find_component(int n) { memset(ord,0,sizeof(ord)); memset(instk,0,sizeof(instk)); cnt=0,scnt=0,stk[0]=0; for(int i=1;i<=n;i++) if(!ord[i]) tarjan(i); } int main() { int n,m,x,y,i,t,ans; pointer ptr; while(scanf("%d",&n),n) { scanf("%d",&m); for(i=1;i<=n;i++) g[i]=r[i]=NULL; for(i=1;i<=m;i++) { scanf("%d%d",&x,&y); insert(x,y,g); } find_component(n); memset(map,0,sizeof(map)); for(i=1;i<=n;i++) { ptr=g[i]; while(ptr!=NULL) { t=ptr->ver; if(id[i]!=id[t]) map[id[i]]=1; ptr=ptr->next; } } ans=0; for(i=1;i<=scnt;i++) if(!map[i]) { ptr=r[i]; while(ptr!=NULL) { result[++ans]=ptr->ver; ptr=ptr->next; } } qsort(result+1,ans,sizeof(result[1]),cmp); for(i=1;i<=ans;i++) { if(i>1) printf(" "); printf("%d",result[i]); } printf("/n"); } return 0; }
