思路：将所有强连通分支找出来，并进行缩点，然后找其中所有出度为0的连通分支，就是题目要求的。
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<queue> #define Maxn 5100 #define Maxm Maxn*100 #define inf 0x7fffffff using namespace std; int index[Maxn],vi[Maxn],stack[Maxn],dfn[Maxn],low[Maxn],e,n,lab,top,num,list,mark[Maxn],degree[Maxn],be[Maxn]; struct Edge{ int from,to,next; }edge[Maxm]; void addedge(int from,int to) { edge[e].from=from; edge[e].to=to; edge[e].next=index[from]; index[from]=e++; } void init() { memset(index,-1,sizeof(index)); memset(degree,0,sizeof(degree)); memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(vi,0,sizeof(vi)); memset(mark,0,sizeof(mark)); memset(be,0,sizeof(be)); e=lab=top=num=list=0; } void Out(int u)//将该连通分量的点进行统计 { int i,j; list++; do{ i=stack[--top]; be[i]=list; vi[i]=0; mark[i]=1; } while(i!=u); } int dfs(int u) { dfn[u]=low[u]=++lab; stack[top++]=u; vi[u]=1; int i,j,temp; for(i=index[u];i!=-1;i=edge[i].next) { temp=edge[i].to; if(!dfn[temp]) { dfs(temp); low[u]=min(low[u],low[temp]); } if(vi[temp]) low[u]=min(low[u],dfn[temp]); } if(low[u]==dfn[u])//找到连通分量 Out(u); return 0; } int solve() { int i,j,temp; for(i=1;i<=n;i++) if(!dfn[i]) dfs(i); memset(vi,1,sizeof(vi)); for(i=1;i<=n;i++) { for(j=index[i];j!=-1;j=edge[j].next) { temp=edge[j].to; if(be[i]!=be[temp]) { vi[be[i]]=0; } } } for(i=1;i<=n;i++) { if(mark[i]) { if(vi[be[i]]) { printf("%d",i); break; } } } for(i++;i<=n;i++) { if(mark[i]) { if(vi[be[i]]) printf(" %d",i); } } printf(" "); return 0; } int main() { int m,i,j,a,b; while(scanf("%d",&n)!=EOF,n) { scanf("%d",&m); init(); for(i=1;i<=m;i++) { scanf("%d%d",&a,&b); addedge(a,b); } solve(); } return 0; }