Advertisement
Guest User

Untitled

a guest
Nov 20th, 2017
63
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.99 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <stack>
  4.  
  5. using namespace std;
  6.  
  7. vector<int> used;
  8. vector< vector<int> > G;
  9. stack<int> ans;
  10. int n, m;
  11.  
  12. void dfs(int start) {
  13.     used[start] = 1;
  14.     for(int i = 0; i < n; i++) {
  15.         if(used[i] == 0 && G[start][i] == 1) {
  16.             dfs(i);
  17.         }
  18.     }
  19.     used[start] = 2;
  20.     ans.push(start);
  21. }
  22.  
  23. int main() {
  24.     cin >> n >> m;
  25.     G = vector< vector<int> >(n, vector<int>(n, 0));
  26.     for(int i = 0; i < m; i++) {
  27.         int a, b;
  28.         cin >> a >> b;
  29.         G[a - 1][b - 1] = 1;
  30.     }
  31.     used = vector<int>(n, 0);
  32.     vector<int> a;
  33.     for(int i = 0; i < n; i++) {
  34.         int sum = 0;
  35.         for(int j = 0; j < m; j++) {
  36.             sum += G[j][i];
  37.         }
  38.         if(sum == 0) {
  39.             a.push_back(i);
  40.         }
  41.     }
  42.     for(int i = 0; i < a.size(); i++) {
  43.         dfs(a[i]);
  44.     }
  45.     while(!ans.empty()) {
  46.         cout << ans.top() + 1 << ' ';
  47.         ans.pop();
  48.     }
  49.     return 0;
  50. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement