The Bottom of a Graph 强连通分量加缩点
/*题意比较晦涩，大致就是求一个图缩点后出度为0的点的个数。*/#include <stdio.h>#include <cstring>#include <vector>#include <iostream>using namespace std;vector<int> e[5010];int dfn[5001];int low[5001];int stack[5001];bool instack[5001];int belong[5001];int out[5001];int n,m,num,top,cnt;void tarjan(int u){ int j; stack[top++]=u; low[u]=dfn[u]=++num; instack[u]=true; for(int i=0; i<e[u].size(); i++) { int v=e[u][i]; if(!dfn[v]) { tarjan(v); low[u]=min(low[v],low[u]); } else if(instack[v]) low[u]=min(dfn[v],low[u]); } if(low[u]==dfn[u]) { cnt++; do { j=stack[--top]; instack[j]=false; belong[j]=cnt; } while(j!=u); }}int main(){ while(scanf("%d",&n)==1) { if(n==0) break; scanf("%d",&m); int a,b; for(int i=1; i<=n; i++) e[i].clear(); top=0; num=0; cnt=0; while(m--) { scanf("%d%d",&a,&b); e[a].push_back(b); } memset(low,0,sizeof(low)); memset(dfn,0,sizeof(dfn)); memset(instack,false,sizeof(instack)); memset(belong,0,sizeof(belong)); for(int i=1; i<=n; i++) { out[i]=0; if(!dfn[i]) tarjan(i); } for(int i=1; i<=n; i++) { int len=e[i].size(); for(int j=0; j<len; j++) { if(belong[i]!=belong[e[i][j]]) out[belong[i]]++; } } int k=0; for(int i=1; i<=n; i++) { if(out[belong[i]]==0) { if(k++) printf(" "); printf("%d",i); } } printf("\n"); } return 0;}