Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <stack>
- #include <algorithm>
- #include <cstring>
- using namespace std;
- int m; int n;
- bool visited[300005];
- stack<int>s;
- vector<int>graph[300005];
- vector<int>rev_graph[300005];
- void dfs(int node){
- visited[node]=true;
- for(int i=0; i<graph[node].size(); i++){
- int sosed=graph[node][i];
- if(visited[sosed]==false){
- dfs(sosed);
- }
- }
- s.push(node);
- }
- void rev_dfs(int r_node){
- visited[r_node]=true;
- cout<<r_node<<" ";
- for(int i=0; i<rev_graph[r_node].size(); i++){
- int rev_sosed=rev_graph[r_node][i];
- if(visited[rev_sosed]==false){
- rev_dfs(rev_sosed);
- }
- }
- }
- int main()
- {
- cin>> n >> m;
- for(int i=0; i<m; i++){
- int a, b;
- cin>>a>>b;
- a--;
- b--;
- graph[b].push_back(a);
- rev_graph[a].push_back(b);
- }
- memset(visited, false, sizeof visited);
- for(int i=0; i<n; i++){
- if(visited[i]==false){
- dfs(i);
- }
- }
- memset(visited,false , sizeof visited);
- while(!s.empty()){
- int node=s.top();
- if(visited[node]==false){
- rev_dfs(node);
- cout<<endl;
- }
- s.pop();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement