Nik_Perepelov

Даше исправленное

Nov 3rd, 2021 (edited)
958
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.00 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. int n, m;
  7. vector<vector<int>> G(20000);
  8. vector<vector<int>> GR(20000);
  9. vector<int> used(20000);
  10. vector<int> order;
  11. vector<int> comp;
  12.  
  13. void dfs(int v) {
  14.     used[v] = 1;
  15.     for (int i = 0; i < G[v].size(); i++) {
  16.         int actual_v = G[v][i];
  17.         if (used[actual_v] == 0) {
  18.             dfs(actual_v);
  19.         }
  20.     }
  21.     order.push_back(v);
  22. }
  23.  
  24. void dfs_R(int v) {
  25.     used[v] = 1;
  26.     comp.push_back(v);
  27.     for (int i = 0; i < GR[v].size(); i++) {
  28.         int actual_v = GR[v][i];
  29.         if (used[actual_v] == 0) {
  30.             dfs_R(actual_v);
  31.         }
  32.     }
  33. }
  34.  
  35. int main() {
  36.     cin >> n >> m;
  37.     for (int i = 0; i < m; i++) {
  38.         int f, t;
  39.         cin >> f >> t;
  40.         G[f - 1].push_back(t - 1);
  41.         GR[t - 1].push_back(f - 1);
  42.     }
  43.  
  44.     for (int i = 0; i < n; i++) {
  45.         if (used[i] == 0) {
  46.             dfs(i);
  47.         }
  48.     }
  49.  
  50.     for (int i = 0; i < n; i++) {
  51.         used[i] = 0;
  52.     }
  53.  
  54.     int k = 1;
  55.     vector<int> comp_number(n);
  56.     vector<int> comp_v;
  57.     for (int i = 0; i < n; i++) {
  58.         int actual_v = order[n - i - 1];
  59.         if (used[actual_v] == 0) {
  60.             dfs_R(actual_v);
  61.             for (int j = 0; j < comp.size(); j++) {
  62.                 comp_number[comp[j]] = k;
  63.             }
  64.             comp_v.push_back(comp[0]);
  65.             k = k + 1;
  66.             comp.clear();
  67.         }
  68.     }
  69.  
  70.     vector<int> FS(k - 1);
  71.  
  72.     int st = k;
  73.     for (int i = 0; i < n; i++) {
  74.         for (int j = 0; j < G[i].size(); j++) {
  75.             int a = i;
  76.             int b = G[i][j];
  77.             if (comp_number[a] != comp_number[b]) {
  78.                 if (FS[comp_number[a] - 1] == 0)
  79.                     st = st - 1;
  80.                 FS[comp_number[a] - 1] = 1;
  81.             }
  82.         }
  83.     }
  84.     cout << st - 1 << endl;
  85.     for (int i = 0; i < k - 1; i++) {
  86.         if (FS[i] == 0) {
  87.             cout << comp_v[i] + 1 << endl;
  88.         }
  89.     }
  90.     return 0;
  91. }
Advertisement
Add Comment
Please, Sign In to add comment