Доп контест Даше

// 1 задача
#include <iostream>
#include <vector>

using namespace std;

vector<int> root;
vector<int> sizes;
vector<vector<int>> cat_per_cage;

void set_dsu(int n) {
    root.resize(n);
    sizes.resize(n, 1);
    cat_per_cage.resize(n);
    for (int i = 0; i < n; i++) {
        root[i] = i;
        cat_per_cage[i].emplace_back(i);
    }
}

int find_root(int v) {
    if (root[v] == v)
        return v;
    return root[v] = find_root(root[v]);
}

void union_sets(int v, int u) {
    v = find_root(v);
    u = find_root(u);
    if (v != u) {
        if (sizes[v] < sizes[u])
            swap(v, u);

        cat_per_cage[v].resize(cat_per_cage[v].size() + cat_per_cage[u].size());
        for (int i = 0; i < cat_per_cage[u].size(); i++){
            cat_per_cage[v][cat_per_cage[v].size() - cat_per_cage[u].size() + i] = cat_per_cage[u][i];
        }
        cat_per_cage[u].clear();
        root[u] = v;
        sizes[v] += sizes[u];
    }
}

void print_cats(){
    int final_root = find_root(0);
    for (int i = 0; i < cat_per_cage[final_root].size(); i++){
        cout << cat_per_cage[final_root][i] + 1 << ' ';
    }
}


int main() {
    int n, v1, v2;
    cin >> n;
    set_dsu(n);
    for (int i = 0; i < n - 1; i++) {
        cin >> v1 >> v2;
        union_sets(--v1, --v2);
    }
    print_cats();
    return 0;
}

// 2 задача
#include <iostream>
#include <vector>

using namespace std;

struct command {
    int type;
    int v1;
    int v2;
};

int n, k;
vector<int> root;
vector<int> sizes;
vector<vector<int>> cat_per_cage;
vector<bool> ans;

void set_dsu(int n) {
    root = vector<int>(n);
    sizes = vector<int>(n, 1);
    cat_per_cage = vector<vector<int>>(n);
    for (int i = 0; i < n; i++) {
        root[i] = i;
        cat_per_cage[i].emplace_back(i);
    }
}

int find_root(int v) {
    if (root[v] == v)
        return v;
    return root[v] = find_root(root[v]);
}

void union_sets(int v, int u) {
    v = find_root(v);
    u = find_root(u);
    if (v != u) {
        if (sizes[v] < sizes[u]) {
            int tmp = v;
            v = u;
            u = tmp;
        }

        cat_per_cage[v].resize(cat_per_cage[v].size() + cat_per_cage[u].size());
        for (int i = 0; i < cat_per_cage[u].size(); i++){
            cat_per_cage[v][cat_per_cage[v].size() - cat_per_cage[u].size() + i] = cat_per_cage[u][i];
        }
        cat_per_cage[u].clear();
        root[u] = v;
        sizes[v] += sizes[u];
    }
}

void solve() {
    int m;
    cin >> m >> k;
    if (k == 0)
        exit(0);
    vector<command> commands(k);
    for (int i = 0; i < 2 * m; i++) {
        int trash;
        cin >> trash;
    }
    for (int i = 0; i < k; i++) {
        string command_type;
        cin >> command_type;
        if (command_type == "cut") {
            commands[i].type = 2;
        } else {
            commands[i].type = 1;
        }
        int a, b;
        cin >> a >> b;
        b--;
        commands[i].v1 = a - 1;
        commands[i].v2 = b;
    }


    for (int i = k - 1; i >= 0; i--) {
        if (commands[i].type == 1)
            ans.push_back(find_root(commands[i].v1) == find_root(commands[i].v2));
        else
            union_sets(commands[i].v1, commands[i].v2);
    }

    for (int u = ans.size() - 1; u >= 0; u--) {
        if (ans[u])
            cout << "YES\n";
        else
            cout << "NO\n";
    }
}


int main() {
    cin >> n;
    set_dsu(n);
    solve();
    return 0;
}
// 3 задача

#include <iostream>
#include <vector>

using namespace std;

int n, m;
vector<vector<int>> g;
vector<int> stroi;
vector<int> state;
int flag = false;

void dfs(int v, int parent) {
    state[v] = 1;
    for (auto &i: g[v]) {
        if (state[i] == 1) {
            flag = true;
            return;
        }
        if (state[i] == 0) {
            dfs(i, v);
            if (flag)
                return;
        }
    }
    stroi.push_back(v);
    state[v] = 2;
}

void input() {
    cin >> n >> m;

    state.resize(n);
    g.resize(n);

    for (int i = 0; i < m; i++) {
        int fr, to;
        cin >> fr >> to;
        fr--;
        to--;
        g[fr].emplace_back(to);
    }
}

void solve() {
    for (int i = 0; i < n; i++) {
        if (!state[i]) {
            dfs(i, -1);
            if (flag) {
                cout << "No";
                return;
            }
        }
    }
}

void print() {
    cout << "Yes\n";
    for (int i = 0; i < n; i++) {
        cout << stroi[n - 1 - i] + 1 << ' ';
    }
}


int main() {

    input();
    solve();
    if (flag)
        return 0;
    print();


    return 0;
}

// 4 задача
#include <iostream>
#include <vector>

using namespace std;

struct command {
    int type;
    int v1;
    int v2;
};

int n, k;
vector<int> root;
vector<int> sizes;
vector<vector<int>> cat_per_cage;
vector<bool> ans;

void set_dsu(int n) {
    root = vector<int>(n);
    sizes = vector<int>(n, 1);
    k = 0;
    cat_per_cage = vector<vector<int>>(n);
    for (int i = 0; i < n; i++) {
        root[i] = i;
        cat_per_cage[i].emplace_back(i);
    }
}

int find_root(int v) {
    if (root[v] == v)
        return v;
    return root[v] = find_root(root[v]);
}

void union_sets(int v, int u) {
    v = find_root(v);
    u = find_root(u);
    if (v != u) {
        if (sizes[v] < sizes[u]) {
            int tmp = v;
            v = u;
            u = tmp;
        }

        cat_per_cage[v].resize(cat_per_cage[v].size() + cat_per_cage[u].size());
        for (int i = 0; i < cat_per_cage[u].size(); i++){
            cat_per_cage[v][cat_per_cage[v].size() - cat_per_cage[u].size() + i] = cat_per_cage[u][i];
        }
        cat_per_cage[u].clear();
        root[u] = v;
        sizes[v] += sizes[u];
        k++;
    }
}

void solve() {
    for (int i = 0; i < n; i++){
        int v;
        cin >> v;
        union_sets(i, v - 1);
    }
    cout << n - k;
}


int main() {
    cin >> n;
    set_dsu(n);
    solve();
    return 0;
}
// 7 задача
#include <iostream>
#include <vector>

using namespace std;

struct route {
    int from;
    int to;
    int from_time;
    int to_time;

    route(int _from, int _to, int _from_time, int _to_time) {
        from = _from;
        to = _to;
        from_time = _from_time;
        to_time = _to_time;
    }
};

int n, m, finish, k;
vector<vector<route>> graph;
vector<int> used;
vector<int> village_time;

void dijkstra() {
    for (;;) {
        int min_village = -2;
        int min_time = INT_MAX;
        for (int i = 0; i < n; i++) {
            if (used[i] == 0 && village_time[i] < min_time) {
                min_village = i;
                min_time = village_time[i];
            }
        }
        if (min_village == -2)
            return;
        used[min_village] = 1;
        for (int i = 0; i < graph[min_village].size(); i++){
            if (village_time[min_village] <= graph[min_village][i].from_time && graph[min_village][i].to_time < village_time[graph[min_village][i].to])
                village_time[graph[min_village][i].to] = graph[min_village][i].to_time;
        }
    }
}

void input(){
    cin >> n >> finish >> m;
    finish--;

    graph = vector<vector<route>>(n);
    used = vector<int>(n);
    village_time = vector<int>(n, INT_MAX);

    for (int i = 0; i < m; i++) {
        cin >> k;

        int from, to, old_time, time;
        for (int j = 0; j < k; j++) {
            cin >> to >> time;
            to--;
            if (j > 0) {
                graph[from].push_back(route(from, to, old_time, time));
            }
            from = to;
            old_time = time;
        }
    }
}

void solve(){
    village_time[0] = 0;

    dijkstra();
}

void print(){
    if (village_time[finish] < INT_MAX)
        cout << village_time[finish];
    else
        cout << -1;
}

int main() {
    input();
    solve();
    print();

    return 0;
}
// 8 задача
#include <iostream>
#include <vector>

using namespace std;

struct route {
    int from;
    int to;
    int from_time;
    int to_time;

    route(int _from, int _to, int _from_time, int _to_time) {
        from = _from;
        to = _to;
        from_time = _from_time;
        to_time = _to_time;
    }
};

int n, m, finish, start;
vector<vector<route>> graph;
vector<int> used;
vector<int> village_time;

void dijkstra() {
    for (;;) {
        int min_village = -2;
        int min_time = INT_MAX;
        for (int i = 0; i < n; i++) {
            if (used[i] == 0 && village_time[i] < min_time) {
                min_village = i;
                min_time = village_time[i];
            }
        }
        if (min_village == -2)
            return;
        used[min_village] = 1;
        for (int i = 0; i < graph[min_village].size(); i++){
            if (village_time[min_village] <= graph[min_village][i].from_time && graph[min_village][i].to_time < village_time[graph[min_village][i].to])
                village_time[graph[min_village][i].to] = graph[min_village][i].to_time;
        }
    }
}

void input(){
    cin >> n >> start >> finish >> m;
    start= start-1;
    finish = finish - 1;

    graph = vector<vector<route>>(n);
    used = vector<int>(n);
    village_time = vector<int>(n, INT_MAX);

    for (int i = 0; i < m; i++) {
        int from, departing_time_curr, to, arrival_time_curr;
        cin >> from >> departing_time_curr >> to >> arrival_time_curr;
        from--;
        to--;
        graph[from].push_back(route(from, to, departing_time_curr, arrival_time_curr));
    }
}

void solve(){
    village_time[start] = 0;

    dijkstra();
}

void print(){
    if (village_time[finish] < INT_MAX)
        cout << village_time[finish];
    else
        cout << -1;
}

int main() {
    input();
    solve();
    print();

    return 0;
}