题意:求解点v可达的点都能到达v的点的集合
只需要求出出度为0的强连通分量输出即可。属于简单模板题~~~
#include <iostream> #include <vector> #include <stack> #include <string.h> #include <stdio.h> #include <algorithm> using namespace std; const int N=5005; int vN,e; vector <int >grap[N]; stack<int> s; int low[N]; int num[N]; int visited[N]; int instack[N]; int index; int cnt_scc; int belong[N]; int outdeg[N]; vector<int >ans; void init() { for(int i=0;i<=vN;i++)grap[i].clear(); ans.clear(); while(!s.empty())s.pop(); memset(instack,0,(vN+2)*sizeof(int)); memset(visited,0,(vN+2)*sizeof(int)); memset(low,-1,(vN+2)*sizeof(int)); memset(num,-1,(vN+2)*sizeof(int)); memset(belong,-1,(vN+2)*sizeof(int)); index=0; cnt_scc=0; memset(outdeg,0,(vN+2)*sizeof(int)); } void tarjan(int v) { low[v]=num[v]=++index; s.push(v); instack[v]=1; visited[v]=1; for(int i=0;i<grap[v].size();i++) { int w=grap[v][i]; if(!visited[w]) { tarjan(w); low[v]=min(low[v],low[w]); } else if(instack[w]) { low[v]=min(low[v],low[w]); } } int u; if(low[v]==num[v]) { ++cnt_scc; do { u=s.top(); belong[u]=cnt_scc; s.pop(); instack[u]=0; }while(u!=v); } } int main() { while(cin>>vN&&vN!=0) { cin>>e; int i,j; init(); for(i=0;i<e;i++) { int u,v; scanf("%d%d",&u,&v); grap[u].push_back(v); } for(i=1;i<=vN;i++) { if(!visited[i])tarjan(i); } for(i=1;i<=vN;i++) { for(j=0;j<grap[i].size();j++) { int k=grap[i][j]; if(belong[i]!=belong[k])outdeg[belong[i]]++; } } for(i=1;i<=cnt_scc;i++) { if(outdeg[i]==0) { for(j=1;j<=vN;j++) { if(belong[j]==i)ans.push_back(j); } } } sort(ans.begin(),ans.end()); if(ans.size()==0)cout<<endl; else { for(i=0;i<ans.size();i++)cout<<ans[i]<<" "; cout<<endl; } } return 0; }