7 контест Надару

//1
#include <iostream>
#include <vector>
using namespace std;
vector<int> ordr, actual_comp;
vector<bool> visited;
vector<vector<int>> graph, reversed_graph;

void dfs2(int vertex) {
    visited[vertex] = true;
    actual_comp.push_back(vertex);
    for (int i = 0; i < reversed_graph[vertex].size(); i++)
        if (!visited[reversed_graph[vertex][i]])
            dfs2(reversed_graph[vertex][i]);
}
void dfs1(int vertex) {
    visited[vertex] = true;
    for (int i = 0; i < graph[vertex].size(); i++)
        if (!visited[graph[vertex][i]])
            dfs1(graph[vertex][i]);
    ordr.push_back(vertex);
}



int main() {
    int num_of_vertex, num_of_edges, a, b;
    cin >> num_of_vertex >> num_of_edges;
    visited.resize(num_of_vertex);
    reversed_graph = vector<vector<int>> (num_of_vertex);
    graph = vector<vector<int>> (num_of_vertex);
    for (int i = 0; i < num_of_edges; i++) {
        cin >> a >> b;
        reversed_graph[b - 1].push_back(a - 1);
        graph[a - 1].push_back(b - 1);
    }
    for (int i = 0; i < num_of_vertex; i++)
        if (!visited[i])
            dfs1(i);
    visited.assign(num_of_vertex, false);

    vector<int> answer(num_of_vertex);
    int num_of_components = 0;
    for (int i = 0; i < num_of_vertex; i++) {
        if (visited[ordr[num_of_vertex - i - 1]] == false) {
            dfs2(ordr[num_of_vertex - 1 - i]);
            for (int k = 0; k < actual_comp.size(); k++)
                answer[actual_comp[k]] = num_of_components + 1;
            num_of_components+=1;
            actual_comp.clear();
        }
    }
    cout << num_of_components << endl;
    for (int i = 0; i < num_of_vertex; i++) {
        cout << answer[i]<< " ";
    }
}

// 2

#include <iostream>
#include <vector>
using namespace std;
vector<int> ordr, actual_comp;
vector<int> visited;
vector<vector<int>> graph, reversed_graph;
void dfs1(int vertex) {
    visited[vertex] = 1;
    for (int i = 0; i < graph[vertex].size(); i++)
        if (!visited[graph[vertex][i]])
            dfs1(graph[vertex][i]);
    ordr.push_back(vertex);
}
void dfs2(int vertex) {
    visited[vertex] = 1;
    actual_comp.push_back(vertex);
    for (int i = 0; i < reversed_graph[vertex].size(); i++)
        if (!visited[reversed_graph[vertex][i]])
            dfs2(reversed_graph[vertex][i]);
}
int main() {
    int num_of_vertex, num_of_edges;
    cin >> num_of_vertex >> num_of_edges;
    visited.resize(num_of_vertex);
    reversed_graph = vector<vector<int>> (num_of_vertex);
    vector<pair<int,int>> edges;
    vector<int> final;
    graph = vector<vector<int>> (num_of_vertex);
    for (int i = 0; i < num_of_edges; i++) {
        int f;
        int t;
        cin >> f >> t;
        reversed_graph[t - 1].push_back(f - 1);
        graph[f - 1].push_back(t - 1);
        pair<int,int> tmp(f - 1, t - 1);
        edges.push_back(tmp);
    }
    for (int i = 0; i < num_of_vertex; i++)
        if (visited[i] == 0)
            dfs1(i);
    visited.assign(num_of_vertex, 0);

    vector<int> answer(num_of_vertex);
    int num_of_components = 0;
    for (int i = 0; i < num_of_vertex; i++) {
        if (visited[ordr[num_of_vertex - i - 1]] == false) {
            dfs2(ordr[num_of_vertex - 1 - i]);
            for (int k = 0; k < actual_comp.size(); k++)
                answer[actual_comp[k]] = num_of_components + 1;
            num_of_components+=1;
            actual_comp.clear();
        }
    }
    vector<int> firebase(num_of_components);
    for (int i = 0; i < num_of_edges; i++){
        if (answer[edges[i].first] != answer[edges[i].second]){
            firebase[answer[edges[i].first] - 1] = 1;
        }
    }
    for (int i = 0; i < num_of_components; i++){
        if (firebase[i] == 0){
            for (int k = 0; k < num_of_vertex; k++){
                if (answer[k] == i + 1){
                    final.emplace_back(k + 1);
                    break;
                }
            }
        }
    }
    cout << final.size() << endl;
    for (int i = 0; i < final.size(); i++){
        cout << final[i] << '\n';
    }
}