Advertisement
Guest User

Untitled

a guest
Dec 15th, 2018
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.98 KB | None | 0 0
  1. #include <vector>
  2. #include <iostream>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. vector<int> in[100000], out[100000];
  8. int used[100000];
  9. vector<int> done;
  10. int prev1[100000];
  11. vector<int> ans, res;
  12. int a, b;
  13.  
  14. int dfs(int u)
  15. {
  16.     if (used[u] == 1)
  17.         return 0;
  18.     if (u == b)
  19.     {
  20.         int v = b;
  21.         while (v != -1)
  22.         {  
  23.             res.push_back(v);
  24.             v = prev1[v];
  25.         }
  26.         reverse(res.begin(), res.end());
  27.  
  28.         return 1;
  29.     }
  30.  
  31.     used[u] = 1;
  32.     for (int j = 0; j < out[u].size(); j++)
  33.     {
  34.         int v = out[u][j];
  35.         if (!used[v])
  36.         {
  37.             prev1[v] = u;
  38.             if (dfs(v))
  39.                 return 1;
  40.         }
  41.     }
  42.     return 0;
  43. }
  44.  
  45. int main()
  46. {
  47.     cout.sync_with_stdio(0);
  48.     int n, m, p, q;
  49.     cin >> n >> m >> a >> b;
  50.     a--, b--;
  51.  
  52.     for (int i = 0; i < n; i++)
  53.         used[i] = 0;
  54.  
  55.     for (int i = 0; i < m; i++)
  56.     {
  57.         cin >> p >> q;
  58.         out[p - 1].push_back(q - 1);
  59.         in[q - 1].push_back(p - 1);
  60.     }
  61.  
  62.     prev1[a] = -1;
  63.  
  64.     dfs(a);
  65.    
  66.     int cnt = 0;
  67.     int k = (int)res.size();
  68.     int up[k], down[k];
  69.     for (int i = 0; i < k; i++)
  70.     {
  71.         up[i] = 0;
  72.         if (!i)
  73.             down[i] = 0;
  74.         else
  75.             down[i] = 1;
  76.     }
  77.     for (int i = 0; i < (int)res.size(); i++)
  78.     {
  79.         if (i > 0)
  80.             up[i - 1] = -1;
  81.         down[i] = 0;
  82.         for (int j = 0; j < in[i].size(); j++)
  83.         {
  84.             int v = in[i][j];
  85.             cnt += up[v];
  86.         }
  87.         //cout << res[i] + 1 << " " << cnt << endl;
  88.         if (cnt == 0 && res[i] != a && res[i] != b)
  89.             ans.push_back(res[i] + 1);
  90.         for (int j = 0; j < out[i].size(); j++)
  91.         {
  92.             int v = out[i][j];
  93.             cnt += down[v];
  94.         }
  95.     }
  96.     cout << ans.size() << endl;
  97.     sort(ans.begin(), ans.end());
  98.     for (int i = 0; i < (int)ans.size(); i++)
  99.         cout << ans[i] << " ";
  100. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement