7, 8 контест Александру

// 1
#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> graph, reversed_graph;
vector<int> order, current_component;
vector<bool> used;

void dfs(int u) {
    used[u] = true;
    for (int i = 0; i < graph[u].size(); i++)
        if (!used[graph[u][i]])
            dfs(graph[u][i]);
    order.emplace_back(u);
}

void reversed_dfs(int u) {
    used[u] = true;
    current_component.push_back(u);
    for (int i = 0; i < reversed_graph[u].size(); i++)
        if (!used[reversed_graph[u][i]])
            reversed_dfs(reversed_graph[u][i]);
}

int main() {
    int n, m;
    cin >> n >> m;
    reversed_graph = vector<vector<int>> (n);
    used = vector<bool> (n);
    graph = vector<vector<int>> (n);
    for (int i = 0; i < m; i++) {
        int from, to;
        cin >> from >> to;
        graph[from - 1].push_back(to - 1);
        reversed_graph[to-1].push_back(from - 1);
    }
    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            dfs(i);
        }
    }
    used = vector<bool> (n);

    vector<int> answer(n);
    int counter = 0;
    for (int i = 0; i < n; i++) {
        if (!used[order[n - 1 - i]]) {
            reversed_dfs(order[n - 1 - i]);
            for (int j = 0; j < current_component.size(); j++){
                answer[current_component[j]] = counter;
            }
            current_component.clear();
            counter++;
        }
    }
    cout << counter << endl;
    for (int i = 0; i < answer.size(); i++) {
        cout << answer[i] + 1<< " ";
    }
}

// 2
#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> graph, reversed_graph;
vector<int> order, current_component;
vector<bool> used;

void dfs(int u) {
    used[u] = true;
    for (int i = 0; i < graph[u].size(); i++)
        if (!used[graph[u][i]])
            dfs(graph[u][i]);
    order.emplace_back(u);
}
void reversed_dfs(int u) {
    used[u] = true;
    current_component.push_back(u);
    for (int i = 0; i < reversed_graph[u].size(); i++)
        if (!used[reversed_graph[u][i]])
            reversed_dfs(reversed_graph[u][i]);
}

int main() {
    int n, m;
    cin >> n >> m;

    used = vector<bool> (n);
    graph = vector<vector<int>> (n);
    reversed_graph = vector<vector<int>> (n);
    vector<pair<int,int>> edges(m);
    vector<int> answer;
    for (int i = 0; i < m; i++) {
        int fr, to;
        cin >> fr >> to;
        graph[fr-1].emplace_back(to-1);
        reversed_graph[to-1].emplace_back(fr-1);
        edges[i] = make_pair(fr-1, to-1);
    }
    for (int i = 0; i < n; i++)
        if (!used[i])
            dfs(i);
    used = vector<bool> (n);

    vector<int> component_number(n);
    int counter = 0;
    for (int i = 0; i < n; ++i) {
        if (!used[order[n - 1 - i]]) {
            reversed_dfs(order[n - 1 - i]);
            for (int j = 0; j < current_component.size(); j++){
                component_number[current_component[j]] = counter;
            }
            current_component.clear();
            counter++;
        }
    }
    vector<bool> is_fb_needed(counter, true);
    for (int i = 0; i < m; i++){
        if (component_number[edges[i].first] != component_number[edges[i].second]){
            is_fb_needed[component_number[edges[i].first]] = false;
        }
    }
    for (int i = 0; i < counter; i++){
        if (is_fb_needed[i]){
            for (int j = 0; j < n; j++){
                if (i == component_number[j]){
                    answer.emplace_back(j + 1);
                    break;
                }
            }
        }
    }
    cout << answer.size() << endl;
    for (int i = 0; i < answer.size(); i++){
        cout << answer[i] << endl;
    }
}

// 8.1
#include <iostream>
#include <vector>
using namespace std;

struct FlowEdge {
    int to;
    long long capacity,flow;
    FlowEdge(int to_, long long capacity_, long long flow_){
        to=to_;
        capacity=capacity_;
        flow=flow_;
    }
};

int n, start = 0, finish;
vector<FlowEdge> edges;
vector<vector<int>> graph;
vector<int> level, queue, pointer;

void add_edge(int from, int to, long long capacity){
    graph[to].emplace_back(edges.size());
    edges.emplace_back(from, 0, 0);
    graph[from].emplace_back(edges.size());
    edges.emplace_back(to, capacity, 0);
}
long long dfs (int u, long long flow) {
    if (!flow)
        return 0;
    if (u == finish)
        return flow;
    for (; pointer[u] < graph[u].size(); pointer[u]++){
        int edge_number = graph[u][pointer[u]], to = edges[edge_number].to;
        if (level[to] != level[u] + 1)
            continue;
        long long blocking_flow = dfs(to, min(edges[edge_number].capacity - edges[edge_number].flow, flow));
        if (blocking_flow) {
            edges[edge_number].flow += blocking_flow;
            edges[edge_number + 1].flow -= blocking_flow;
            return blocking_flow;
        }
    }
    return 0;
}
bool bfs() {
    int queue_pointer = 0, queue_size = 0;
    queue[queue_size] = start;
    queue_size++;
    level = vector<int> (n, -1);
    level[start] = 0;
    while (queue_pointer < queue_size && level[finish] == -1){
        int current_v = queue[queue_pointer];
        queue_pointer++;
        for (int i = 0; i < graph[current_v].size(); i++){
            int edge_number = graph[current_v][i], to = edges[edge_number].to;
            if (level[to] == -1 && edges[edge_number].capacity > edges[edge_number].flow){
                level[to] = level[current_v] + 1;
                queue[queue_size] = to;
                queue_size++;
            }
        }
    }
    return level[finish] != -1;
}



void dinic() {
    long long flow = 0;
    while(true) {
        if (!bfs()) {
            cout << flow;
            exit(0);
        }
        pointer = vector<int> (n);
        while (long long adding_flow = dfs(start, 2e9))
            flow += adding_flow;
    }
}

int main() {
    int m;
    cin >> n >> m;
    queue = vector<int> (n);
    graph = vector<vector<int>> (n);
    for (int i = 0; i < m; i++){
        int from, to, capacity;
        cin >> from >> to >> capacity;
        from--; to--;
        add_edge(from, to, capacity);
    }
    finish = n - 1;
    dinic();
}