Advertisement
Guest User

Untitled

a guest
Mar 28th, 2017
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.60 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdio>
  4. #include <string>
  5. #include <cmath>
  6. #include <algorithm>
  7.  
  8. using namespace std;
  9.  
  10. vector<vector<int> > g;
  11. vector<int> order, used, check;
  12. vector<pair<int, int> > edge;
  13.  
  14. void dfs(int v)
  15. {
  16.     used[v] = 1;
  17.     for (int i = 0; i < g[v].size(); i++)
  18.     {
  19.         int to = g[v][i];
  20.         if (!used[to])
  21.             dfs(to);
  22.     }
  23.     order.push_back(v);
  24. }
  25.  
  26. int main()
  27. {
  28.     int n, m;
  29.     cin >> n >> m;
  30.  
  31.     g.resize(n);
  32.     check.assign(n, 0);
  33.  
  34.     int x, y;
  35.     for (int i = 0; i < n; i++)
  36.     {
  37.         cin >> x >> y;
  38.         x--;
  39.         y--;
  40.         g[x].push_back(y);
  41.     }
  42.  
  43.     used.assign(n, 0);
  44.     for (int i = 0; i < n; i++)
  45.     {
  46.         if (!used[i])
  47.             dfs(i);
  48.     }
  49.  
  50.     check[0] = -1;
  51.  
  52.     for (int i = order.size() - 1; i >= 0; i--)
  53.     {
  54.         int v = order[i];
  55.         for (int j = 0; j < g[v].size(); j++)
  56.         {
  57.             int to = g[v][j];
  58.             edge.push_back({ v, to });
  59.         }
  60.     }
  61.  
  62.     for (int i = 0; i < edge.size(); i++)
  63.     {
  64.         int to = edge[i].second;
  65.         int from = edge[i].first;
  66.         if (check[from] == 0)
  67.             continue;
  68.         if (check[to] == -1)
  69.             continue;
  70.         if (check[to] == 0)
  71.         {
  72.             if (check[from] == -1)
  73.                 check[to] = i+1;
  74.             else
  75.             {
  76.                 check[to] = check[from];
  77.             }
  78.         }
  79.         else
  80.             if (check[from] == -1)
  81.             {
  82.                 check[to] = -1;
  83.             }
  84.             else
  85.             {
  86.                 if (check[from] != check[to])
  87.                     check[to] = -1;
  88.                 /*if(check[to] > 0 && check[from] > 0)
  89.                     check[to] = min(check[to], check[from]);*/
  90.             }
  91.     }
  92.  
  93.     int ans = 0;
  94.     for (int i = 0; i < n; i++)
  95.         if (check[i] <= 0)
  96.             ans++;
  97.  
  98.     cout << ans << endl;
  99.  
  100.     for (int i = 0; i < n; i++)
  101.         if (check[i] <= 0)
  102.             cout << i + 1 << " ";
  103.  
  104.     return 0;
  105. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement