Дополнительный контест для Насти

// 1

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> cats;
int m_counter;
vector<int> g;
vector<int> size;

void init(int n) {
    g = vector<int>(n);
    cats.resize(n);
    for (int i = 0; i < n; i++) {
        g[i] = i;
        cats[i].emplace_back(i);
    }
    m_counter = n;
    my_size.resize(n, 1);
    return;
}

int find_parent(int v) {
    if (g[v] == v)
        return v;
    return g[v] = find_parent(g[v]);
}

void try_join_sets(int s1, int s2) {
    s1 = find_parent(s1);
    s2 = find_parent(s2);
    if (s1 != s2) {
        if (size[s1] < size[s2])
            swap(s1, s2);
        g[s2] = s1;
        size[s1] += size[s2];
        m_counter--;

        cats[s1].insert(cats[s1].end(), cats[s2].begin(), cats[s2].end());
        cats[s2].clear();
    }
    return;
}


int main() {
    int n;
    cin >> n;
    init(n);
    for (int i = 1; i < n; i++) {
        int v1, v2;
        cin >> v1 >> v2;
        try_join_sets(v1 - 1, v2 - 1);
    }

    for (auto &cat: cats[find_parent(0)]) {
        cout << cat + 1 << ' ';
    }
    return 0;
}

// 2

#include <iostream>
#include <vector>

using namespace std;

struct query {
    int type;
    int from;
    int to;
};

//vector<vector<int>> cats;
int m_counter;
vector<int> g;
vector<int> my_size;

void init(int n) {
    g = vector<int>(n);
    //cats.resize(n);
    for (int i = 0; i < n; i++) {
        g[i] = i;
        //cats[i].emplace_back(i);
    }
    m_counter = n;
    my_size.resize(n, 1);
    return;
}

int find_parent(int v) {
    if (g[v] == v)
        return v;
    return g[v] = find_parent(g[v]);
}

void try_join_sets(int s1, int s2) {
    s1 = find_parent(s1);
    s2 = find_parent(s2);
    if (s1 != s2) {
        if (my_size[s1] < my_size[s2])
            swap(s1, s2);
        g[s2] = s1;
        my_size[s1] += my_size[s2];
        m_counter--;
        /*
        cats[s1].insert(cats[s1].end(), cats[s2].begin(), cats[s2].end());
        cats[s2].clear();
    */
    }
    return;
}


int main() {
    int n, m, k;
    cin >> n >> m >> k;
    if (k == 0)
        return 0;
    init(n);
    vector<query> q(k);
    vector<bool> answer;
    int musor;
    for (int i = 0; i < m; i++) {
        cin >> musor >> musor;
    }
    string type;
    int a, b;
    for (int i = 0; i < k; i++) {
        cin >> type >> a >> b;
        if (type == "ask")
            q[i].type = 1;
        else
            q[i].type = 2;
        q[i].from = a - 1;
        q[i].to = b - 1;
    }

    for (int i = k - 1; i >= 0; i--) {
        if (q[i].type == 1)
            answer.push_back(find_parent(q[i].from) == find_parent(q[i].to));
        else
            try_join_sets(q[i].from, q[i].to);
    }

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

    return 0;
}

// 3

#include <iostream>
#include <vector>

using namespace std;

int n;
vector<int> order;
vector<int> colour; // 0 - не посещена, 1 - активна, 2 - посещена
vector<vector<int>> graph;

void dfs(int v){
    colour[v] = 1;
    for (auto &i : graph[v]){
        if (colour[i] == 0)
            dfs(i);
        if (colour[i] == 1){
            cout << "No";
            exit(0);
        }
    }
    order.push_back(v);
    colour[v] = 2;
}

void solve(){
    int m;
    int fr, to;
    cin >> n >> m;
    colour = vector<int>(n);
    graph = vector<vector<int>>(n);
    for (int i = 0; i < m; i++){
        cin >> fr >> to;
        graph[fr - 1].emplace_back(to - 1);
    }
    for (int i = 0; i < n; i++){
        if (!colour[i]){
            dfs(i);
        }
    }
    cout << "Yes" << endl;
    for (int i = n - 1; i >= 0; i--){
        cout << order[i] + 1 << ' ';
    }
    return;
}

int main() {
    solve();

    return 0;
}

// 4
#include <iostream>
#include <vector>

using namespace std;

struct query {
    int type;
    int from;
    int to;
};

//vector<vector<int>> cats;
int m_counter;
vector<int> g;
vector<int> my_size;

void init(int n) {
    g = vector<int>(n);
    //cats.resize(n);
    for (int i = 0; i < n; i++) {
        g[i] = i;
        //cats[i].emplace_back(i);
    }
    m_counter = n;
    my_size.resize(n, 1);
    return;
}

int find_parent(int v) {
    if (g[v] == v)
        return v;
    return g[v] = find_parent(g[v]);
}

void try_join_sets(int s1, int s2) {
    s1 = find_parent(s1);
    s2 = find_parent(s2);
    if (s1 != s2) {
        if (my_size[s1] < my_size[s2])
            swap(s1, s2);
        g[s2] = s1;
        my_size[s1] += my_size[s2];
        m_counter--;
        /*
        cats[s1].insert(cats[s1].end(), cats[s2].begin(), cats[s2].end());
        cats[s2].clear();
    */
    }
    return;
}


int main() {
    int n;
    cin >> n;
    init(n);
    for (int i = 0; i < n;i++){
        int a;
        cin >> a;
        try_join_sets(i, a - 1);
    }
    cout << m_counter;

    return 0;
}

// 7
#include <iostream>
#include <vector>

using namespace std;



int n, finish;
vector<int> used;
vector<vector<pair<pair<int,int>, int>>> graph;
vector<int> v_distance;

void dijkstra() {
    v_distance[0] = 0;
    while (true) {
        int min_id = -1;
        int min_distance = 1000000000;
        for (int i = 0; i < n; i++) {
            if (!used[i] && v_distance[i] < min_distance) {
                min_distance = v_distance[i];
                min_id = i;
            }
        }
        if (min_id == -1)
            break;
        used[min_id] = true;
        for (auto &i : graph[min_id]){
            if (i.second < v_distance[i.first.first] && i.first.second >= v_distance[min_id])
                v_distance[i.first.first] = i.second;
        }
    }

    if (v_distance[finish] != 1e9)
        cout << v_distance[finish];
    else
        cout << -1;
}

int main() {
    int m, k;
    cin >> n >> finish >> m;
    finish--;

    graph.resize(n);
    used.resize(n);
    v_distance.resize(n, 1000000000);

    int from, to, t1, t2;
    for (int i = 0; i < m; i++) {
        cin >> k;
        for (int j = 0; j < k; j++) {
            cin >> to >> t2;
            to-=1;
            if (j > 0) {
                graph[from].push_back(make_pair(make_pair(to, t1), t2));
            }
            from = to; t1 = t2;
        }
    }

    dijkstra();
    return 0;
}

// 8
#include <iostream>
#include <vector>

using namespace std;



int n, finish, start;
vector<int> used;
vector<vector<pair<pair<int,int>, int>>> graph;
vector<int> v_distance;

void dijkstra() {
    v_distance[start] = 0;
    while (true) {
        int min_id = -1;
        int min_distance = 1000000000;
        for (int i = 0; i < n; i++) {
            if (!used[i] && v_distance[i] < min_distance) {
                min_distance = v_distance[i];
                min_id = i;
            }
        }
        if (min_id == -1)
            break;
        used[min_id] = true;
        for (auto &i : graph[min_id]){
            if (i.second < v_distance[i.first.first] && i.first.second >= v_distance[min_id])
                v_distance[i.first.first] = i.second;
        }
    }

    if (v_distance[finish] != 1000000000)
        cout << v_distance[finish];
    else
        cout << -1;
}

int main() {
    int m, k;
    cin >> n >> start >> finish >> m;
    finish--;
    start--;

    graph.resize(n);
    used.resize(n);
    v_distance.resize(n, 1000000000);

    int from, to, t1, t2;
    for (int i = 0; i < m; i++) {
        cin >> from >> t1 >> to >> t2;
        graph[from - 1].push_back(make_pair(make_pair(to - 1, t1), t2));
    }

    dijkstra();
    return 0;
}