| Accepted |
1004K |
297MS |
C++ |
1585B |
求出度為0的強(qiáng)連通分量，可能有多個(gè)，按節(jié)點(diǎn)序號從小到大輸出就行了。
還是用兩次DFS 加 名字不好記 加 還不知道怎么發(fā)音的的那個(gè)算法，第一次原圖DFS確定訪問順序，第二次對翻轉(zhuǎn)過邊的方向得到的新圖DFS
確定強(qiáng)連通分量。
還不太熟，寫了一些時(shí)間。
#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;
}