Advertisement
Nik_Perepelov

Untitled

Nov 3rd, 2021
933
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.67 KB | None | 0 0
  1. #include <iostream>
  2. #include <stack>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. struct Graph {
  8.     int N;
  9.     vector<int> order;
  10.     vector<vector<int>> g;
  11.     vector<vector<int>> g_reversed;
  12.     vector<pair<int,int>> s;
  13.  
  14.     Graph(int V) {
  15.         N = V;
  16.         g = vector<vector<int>>(V);
  17.         g_reversed = vector<vector<int>>(V);
  18.     }
  19.  
  20.     void DFS(int v, vector<bool> &used, stack<int> &s) {
  21.         used[v] = true;
  22.         for (auto i: g[v]) {
  23.             if (!used[i]) {
  24.                 DFS(i, used, s);
  25.             }
  26.         }
  27.         s.push(v);
  28.     }
  29.  
  30.     void DFS_REVERSED(int v, vector<bool> &used) {
  31.         used[v] = true;
  32.         order.push_back(v);
  33.         for (auto i: g_reversed[v]) {
  34.             if (!used[i]) {
  35.                 DFS_REVERSED(i, used);
  36.             }
  37.         }
  38.     }
  39.  
  40.  
  41.     void addEdge(int from, int to) {
  42.         g[from].push_back(to);
  43.         g_reversed[to].push_back(from);
  44.         s.push_back(make_pair(from, to));
  45.     }
  46.  
  47.     void solve() {
  48.         vector<bool> used(N);
  49.         stack<int> Stack;
  50.         for (int i = 0; i < N; i++) {
  51.             if (!used[i]) {
  52.                 DFS(i, used, Stack);
  53.             }
  54.         }
  55.         used.assign(N, false);
  56.         vector<int> component_for_v(N);
  57.         int count = 0;
  58.         while (!Stack.empty()) {
  59.             int a = Stack.top();
  60.             Stack.pop();
  61.             if (!used[a]) {
  62.                 DFS_REVERSED(a, used);
  63.                 for (auto &i: order) {
  64.                     component_for_v[i] = count + 1;
  65.                 }
  66.                 count++;
  67.                 order.clear();
  68.             }
  69.         }
  70.         /*cout << count << endl;
  71.         for (auto &i: component_for_v) {
  72.             cout << i << " ";
  73.         }*/
  74.         vector<bool> isFB(count, true);
  75.  
  76.         for (int i = 0; i < s.size(); i++) {
  77.                 if (component_for_v[s[i].first] != component_for_v[s[i].second]) {
  78.                     isFB[component_for_v[s[i].first] - 1] = false;
  79.                 }
  80.         }
  81.  
  82.         vector<int> answer;
  83.         for (int i = 0; i < count; i++) {
  84.             if (isFB[i]) {
  85.                 for (int j = 0; j < N; j++) {
  86.                     if (component_for_v[j] == i + 1) {
  87.                         answer.push_back(j);
  88.                     }
  89.                 }
  90.             }
  91.         }
  92.         cout << answer.size() << endl;
  93.         for (auto& i : answer) {
  94.             cout << i + 1 << endl;
  95.         }
  96.  
  97.     }
  98. };
  99.  
  100. int main() {
  101.     int n, m;
  102.     cin >> n >> m;
  103.     Graph g(n);
  104.     for (int i = 0; i < m; ++i) {
  105.         int from, to;
  106.         cin >> from >> to;
  107.         g.addEdge(from - 1, to - 1);
  108.     }
  109.     g.solve();
  110. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement