poj 2553 The Bottom of a Graph(強連通分量)

NO IMAGE

題意:求解點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;
}