| Accepted |
1004K |
297MS |
C++ |
1585B |
求出度为0的强连通分量，可能有多个，按节点序号从小到大输出就行了。
还是用两次DFS 加 名字不好记 加 还不知道怎么发音的的那个算法，第一次原图DFS确定访问顺序，第二次对翻转过边的方向得到的新图DFS
确定强连通分量。
还不太熟，写了一些时间。
#include<iostream>
#include<vector>
using namespace std;
vector<int> adj[5001];
vector<int> adj_op[5001];
bool visit[5001];
int father[5001],outagree[5001];
vector<int> finish;
int n,m;
void dfs1(int v)
{
visit[v]=true;
for(int i=0; i<adj[v].size(); i++)
if(!visit[adj[v][i]])
dfs1(adj[v][i]);
finish.push_back(v);
}
void dfs2(int v, int fa)
{
visit[v]=true;
for(int i=0; i<adj_op[v].size(); i++)
if(!visit[adj_op[v][i]])
{
father[adj_op[v][i]]=fa;
dfs2(adj_op[v][i],fa);
}
}
int main()
{
while(cin>>n)
{
if(n==0)break;
cin>>m;
int i,j,s,t;
for(i=1; i<=n; i++)
{
adj[i].clear();
adj_op[i].clear();
}
for(i=1; i<=m; i++)
{
cin>>s>>t;
adj[s].push_back(t);
adj_op[t].push_back(s);
}
finish.clear();
memset(visit, 0, sizeof visit);
for(i=1; i<=n; i++)
if(!visit[i])
dfs1(i);
memset(visit, 0, sizeof visit);
memset(father,0,sizeof father);
int cnt=0;
for(i=finish.size()-1; i>=0; i--)
if(!visit[finish[i]])
{
cnt++;
father[finish[i]]=cnt;
dfs2(finish[i],cnt);
}
//for(i=1; i<=n; i++)
// cout<<i<<' '<<father[i]<<endl;
memset(outagree,0,sizeof outagree);
for(i=1; i<=n; i++)
for(j=0; j<adj[i].size(); j++)
{
if(father[i]!=father[ adj[i][j] ])
outagree[ father[i] ]++;
}
int tt=0;
for(i=1; i<=n; i++)
if(outagree[father[i]]==0)
{
if(tt!=0)cout<<' ';
cout<<i;
tt++;
}
cout<<endl;
}
return 0;
}