学步园

http://poj.org/problem?id=2553

//强连通分支,求出度为0 的强连通分支<br /> #include<iostream><br /> #include<vector><br /> using namespace std;<br /> #define M 5001<br /> vector<int> graph[M];<br /> vector<int> graph_t[M];<br /> bool v[M];<br /> int outdegree[M], father[M];<br /> vector<int> finish;<br /> int n, m;<br /> void dfs1(int now)<br /> {<br /> v[now] = true;<br /> for(int i=0; i<graph[now].size(); i++)<br /> if(!v[graph[now][i]])<br /> dfs1(graph[now][i]);<br /> finish.push_back(now);<br /> }<br /> void dfs2(int now,int fa)<br /> {<br /> v[now] = true;<br /> for(int i=0; i<graph_t[now].size(); i++)<br /> if(!v[graph_t[now][i]])<br /> {<br /> father[graph_t[now][i]] = fa;<br /> dfs2(graph_t[now][i],fa);<br /> }<br /> }<br /> int main()<br /> {<br /> // freopen("in.txt","r",stdin);<br /> int i, j, s, t;<br /> while(scanf("%d",&n)!=EOF)<br /> {<br /> if(n==0)<br /> break;<br /> scanf("%d",&m);<br /> for(i=1; i<=n; i++)<br /> {<br /> graph[i].clear();<br /> graph_t[i].clear();<br /> }<br /> for(i=1; i<=m; i++)<br /> {<br /> scanf("%d %d",&s, &t);<br /> graph[s].push_back(t);<br /> graph_t[t].push_back(s);<br /> }<br /> finish.clear();<br /> memset(v,0,sizeof(v));<br /> for(i=1; i<=n; i++)<br /> if(!v[i])<br /> dfs1(i);<br /> memset(v,0,sizeof(v));<br /> memset(father,0,sizeof(father));<br /> memset(outdegree,0,sizeof(outdegree));<br /> int cnt = 0;<br /> for(i=finish.size()-1; i>=0; i--)<br /> if(!v[finish[i]])<br /> {<br /> cnt++;<br /> father[finish[i]] = cnt;<br /> dfs2(finish[i],cnt);<br /> }<br /> /* cout<<cnt<<endl;<br /> for(i=1; i<=n; i++)<br /> cout<<i<<" "<<father[i]<<endl;*/<br /> for(i=1; i<=n; i++)<br /> for(j=0; j<graph[i].size(); j++)<br /> if(father[i] != father[graph[i][j]])<br /> outdegree[father[i] ]++;<br /> int tt=0;<br /> for(i=1; i<=n; i++)<br /> if(outdegree[father[i]] == 0)<br /> {<br /> if(tt != 0)<br /> printf(" ");<br /> printf("%d",i);<br /> tt++;<br /> }<br /> printf("/n");<br /> }<br /> return 0;<br /> }