7 контест Насте

#include <iostream>
#include <stack>
#include <list>
#include <vector>

using namespace std;

struct Graph {
    int N;
    vector<int> order;
    vector<vector<int>> g;
    vector<vector<int>> g_reversed;

    Graph(int V) {
        N = V;
        g = vector<vector<int>>(V);
        g_reversed = vector<vector<int>>(V);
    }

    void DFS(int v, vector<bool> &used, stack<int> &s) {
        used[v] = true;
        for (auto i: g[v]) {
            if (!used[i]) {
                DFS(i, used, s);
            }
        }
        s.push(v);
    }

    void DFS_REVERSED(int v, vector<bool> &used) {
        used[v] = true;
        order.push_back(v);
        for (auto i: g_reversed[v]) {
            if (!used[i]) {
                DFS_REVERSED(i, used);
            }
        }
    }


    void addEdge(int from, int to) {
        g[from].push_back(to);
        g_reversed[to].push_back(from);
    }

    void solve() {
        vector<bool> used(N);
        stack<int> Stack;
        for (int i = 0; i < N; i++) {
            if (!used[i]) {
                DFS(i, used, Stack);
            }
        }
        used.assign(N, false);
        vector<int> component_for_v(N);
        int count = 0;
        while (!Stack.empty()) {
            int a = Stack.top();
            Stack.pop();
            if (!used[a]) {
                DFS_REVERSED(a, used);
                for (auto &i: order) {
                    component_for_v[i] = count + 1;
                }
                count++;
                order.clear();
            }
        }
        cout << count << endl;
        for (auto &i: component_for_v) {
            cout << i << " ";
        }
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    Graph g(n);
    for (int i = 0; i < m; ++i) {
        int from, to;
        cin >> from >> to;
        g.addEdge(from - 1, to - 1);
    }
    g.solve();
}
//2

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

struct Graph {
    int N;
    vector<int> order;
    vector<vector<int>> g;
    vector<vector<int>> g_reversed;

    Graph(int V) {
        N = V;
        g = vector<vector<int>>(V);
        g_reversed = vector<vector<int>>(V);
    }

    void DFS(int v, vector<bool> &used, stack<int> &s) {
        used[v] = true;
        for (auto i: g[v]) {
            if (!used[i]) {
                DFS(i, used, s);
            }
        }
        s.push(v);
    }

    void DFS_REVERSED(int v, vector<bool> &used) {
        used[v] = true;
        order.push_back(v);
        for (auto i: g_reversed[v]) {
            if (!used[i]) {
                DFS_REVERSED(i, used);
            }
        }
    }


    void addEdge(int from, int to) {
        g[from].push_back(to);
        g_reversed[to].push_back(from);
    }

    void solve() {
        vector<bool> used(N);
        stack<int> Stack;
        for (int i = 0; i < N; i++) {
            if (!used[i]) {
                DFS(i, used, Stack);
            }
        }
        used.assign(N, false);
        vector<int> component_for_v(N);
        int count = 0;
        while (!Stack.empty()) {
            int a = Stack.top();
            Stack.pop();
            if (!used[a]) {
                DFS_REVERSED(a, used);
                for (auto &i: order) {
                    component_for_v[i] = count + 1;
                }
                count++;
                order.clear();
            }
        }
        /*cout << count << endl;
        for (auto &i: component_for_v) {
            cout << i << " ";
        }*/
        vector<bool> isFB(count, true);

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < g[i].size(); j++)
            if (component_for_v[i] != component_for_v[g[i][j]]) {
                isFB[component_for_v[i] - 1] = false;
            }
        }

        vector<int> answer;
        for (int i = 0; i < count; i++) {
            if (isFB[i]) {
                for (int j = 0; j < N; j++) {
                    if (component_for_v[j] == i + 1) {
                        answer.push_back(j);
                    }
                }
            }
        }
        cout << answer.size() << endl;
        for (int i : answer) {
            cout << i + 1 << endl;
        }

    }
};

int main() {
    int n, m;
    cin >> n >> m;
    Graph g(n);
    for (int i = 0; i < m; ++i) {
        int from, to;
        cin >> from >> to;
        g.addEdge(from - 1, to - 1);
    }
    g.solve();
}