Advertisement
Guest User

Untitled

a guest
Mar 28th, 2017
51
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.52 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] == 0)
  69.         {
  70.             if (check[from] == -1)
  71.                 check[to] = i+1;
  72.             else
  73.             {
  74.                 check[to] = check[from];
  75.             }
  76.         }
  77.         else
  78.             if (check[from] != -1)
  79.             {
  80.                 check[to] = -1;
  81.             }
  82.             else
  83.             {
  84.                 if (check[from] != check[to])
  85.                     check[to] = -1;
  86.                 else
  87.                     check[to] = min(check[to], check[from]);
  88.             }
  89.     }
  90.  
  91.     int ans = 0;
  92.     for (int i = 0; i < n; i++)
  93.         if (check[i] <= 0)
  94.             ans++;
  95.  
  96.     cout << ans << endl;
  97.  
  98.     for (int i = 0; i < n; i++)
  99.         if (check[i] <= 0)
  100.             cout << i + 1 << " ";
  101.  
  102.     return 0;
  103. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement