Доп контест Александру

// 1

#include <iostream>
#include <vector>

using namespace std;
vector<int> weight;
struct SNM {
    vector<int> parent;
    vector<vector<int>> v_cats;


    int get_parent(int vertex) {
        if (parent[vertex] == vertex)
            return vertex;
        return parent[vertex] = get_parent(parent[vertex]);
    }

    void join_sets(int m1, int m2) {
        m1 = get_parent(m1);
        m2 = get_parent(m2);
        if (m1 != m2) {
            if (weight[m1] < weight[m2]){
                int temporary = m1;
                m1 = m2;
                m2 = temporary;
            }
            v_cats[m1].insert(v_cats[m1].end(), v_cats[m2].begin(), v_cats[m2].end());
            parent[m2] = m1;
            v_cats[m2].clear();
            weight[m1] += weight[m2];
        }
    }

    void init(int n) {
        parent = vector<int>(n);
        v_cats = vector<vector<int>> (n);
        weight = vector<int>(n, 1);
        for (int i = 0; i < n; i++) {
            v_cats[i].push_back(i);
            parent[i] = i;
        }
    }
};

int main() {
    int n;
    cin >> n;
    SNM snm;
    snm.init(n);

    for (int i = 0; i < n - 1; i++){
        int a, b;
        cin >> a >> b;
        snm.join_sets(a - 1, b - 1);
    }

    int last_parent = snm.get_parent(0);

    for (int i = 0; i < n; i++)
        cout << snm.v_cats[last_parent][i] + 1 << ' ';

    return 0;
}

// 2

#include <iostream>
#include <vector>

using namespace std;

struct SNM {
    int cnt;
    vector<int> parent;
    //vector<vector<int>> v_cats;

    void init(int n) {
        cnt = n;
        parent = vector<int>(n);
        //v_cats = vector<vector<int>> (n);
        for (int i = 0; i < n; i++) {
            //v_cats[i].push_back(i);
            parent[i] = i;
        }
    }

    int get_parent(int vertex) {
        if (parent[vertex] == vertex)
            return vertex;
        parent[vertex] = get_parent(parent[vertex]);
        return parent[vertex];
    }

    void joinSets(int m1, int m2) {
        m1 = get_parent(m1);
        m2 = get_parent(m2);
        if (m1 != m2) {
            parent[m2] = m1;
            //v_cats[m1].insert(v_cats[m1].end(), v_cats[m2].begin(), v_cats[m2].end());
            cnt--;
            //v_cats[m2].clear();
        }
    }
};


int main() {
    int n, m, k, a, b;
    cin >> n >> m >> k;

    SNM snm;
    snm.init(n);
    vector<vector<int>> g(n);
    vector<vector<int>> command(k, vector<int> (3));
    for (int i = 0; i < m; i++){
        cin >> a >> b;
        g[a - 1].push_back(b - 1);
    }

    for (int i = 0; i < k; i++){
        string inp;
        cin >> inp >> a >> b;
        if (inp == "ask"){
            command[k - 1 - i][0] = 1;
            command[k - 1 - i][1] = a - 1;
            command[k - 1 - i][2] = b - 1;
        } else {

            command[k - 1 - i][0] = 2;
            command[k - 1 - i][1] = a - 1;
            command[k - 1 - i][2] = b - 1;
        }
    }

    vector<int> answer;
    for (int i = 0; i < k; i++){
        if (command[i][0] == 1){
            if (snm.get_parent(command[i][1]) == snm.get_parent(command[i][2]))
                answer.push_back(1);
            else{
                answer.push_back(0);
            }
        } else {
            snm.joinSets(command[i][1], command[i][2]);
        }
    }

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

    return 0;
}

// 3

#include <iostream>
#include <vector>

using namespace std;

struct Graph {
    vector<int> color;
    vector<vector<int>> g;
    vector<int> answer;

    void init(int new_n) {
        color.resize(new_n);
        g.resize(new_n);
    }

    void dfs(int v) {
        color[v] = 1;
        for (int i = 0; i < g[v].size(); i++) {
            if (color[g[v][i]] == 1) {
                cout << "No";
                exit(0);
            }
            if (color[g[v][i]] == 0) {
                dfs(g[v][i]);
            }
        }
        color[v] = 2;
        answer.push_back(v + 1);
    }
};

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

    Graph graph;
    graph.init(n);

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        graph.g[a - 1].push_back(b - 1);
    }
    for (int i = 0; i < n; i++) {
        if (graph.color[i] == 0) {
            graph.dfs(i);
        }
    }
    cout << "Yes" << endl;
    for (int i = 0; i < n; i++) {
        cout << graph.answer[n - 1 - i] << ' ';
    }

    return 0;
}

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

using namespace std;

struct SNM {
    int cnt;
    vector<int> parent;
    //vector<vector<int>> v_cats;

    void init(int n) {
        cnt = n;
        parent = vector<int>(n);
        //v_cats = vector<vector<int>> (n);
        for (int i = 0; i < n; i++) {
            //v_cats[i].push_back(i);
            parent[i] = i;
        }
    }

    int get_parent(int vertex) {
        if (parent[vertex] == vertex)
            return vertex;
        parent[vertex] = get_parent(parent[vertex]);
        return parent[vertex];
    }

    void joinSets(int m1, int m2) {
        m1 = get_parent(m1);
        m2 = get_parent(m2);
        if (m1 != m2) {
            parent[m2] = m1;
            //v_cats[m1].insert(v_cats[m1].end(), v_cats[m2].begin(), v_cats[m2].end());
            cnt--;
        }
    }
};


int main() {
    int n;
    cin >> n;
    SNM snm;
    snm.init(n);
    for (int i = 0; i < n; i++){
        int a;
        cin >> a;
        snm.joinSets(i, a - 1);
    }
    cout << snm.cnt;

    return 0;
}

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

using namespace std;

struct Edge {
    int dest;
    int d_time;
    int a_time;

    Edge(int to, int time1, int time2) { // конструктор
        dest = to;
        d_time = time1;
        a_time = time2;
    }
};

struct Graph {

    int n;
    vector<bool> used;
    vector<vector<Edge>> g;
    vector<int> dist;

    void init(int new_n){
        n = new_n;
        used.resize(new_n);
        g.resize(new_n);
        dist.resize(new_n, 1000000000);
        dist[0] = 0;
    }

    void dijkstra() {
        while (true) {
            int min_v = -1, min_dist = 1e9;
            for (int i = 0; i < n; i++) {
                if (!used[i] && dist[i] < min_dist) {
                    min_v = i;
                    min_dist = dist[i];
                }
            }
            if (min_v == -1)
                return;
            used[min_v] = true;
            for (int i = 0; i < g[min_v].size(); i++) {
                if (g[min_v][i].a_time < dist[g[min_v][i].dest] && g[min_v][i].d_time >= dist[min_v])
                    dist[g[min_v][i].dest] = g[min_v][i].a_time;
            }
        }
    }

};

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

    Graph graph;
    graph.init(n);

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

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


    graph.dijkstra();

    if (graph.dist[finish - 1] != 1e9)
        cout << graph.dist[finish - 1];
    else
        cout << -1;


    return 0;
}

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

using namespace std;

struct Edge {
    int dest;
    int d_time;
    int a_time;

    Edge(int to, int time1, int time2) { // конструктор
        dest = to;
        d_time = time1;
        a_time = time2;
    }
};

struct Graph {

    int n;
    vector<bool> used;
    vector<vector<Edge>> g;
    vector<int> dist;

    void init(int new_n, int start){
        n = new_n;
        used.resize(new_n);
        g.resize(new_n);
        dist.resize(new_n, 1000000000);
        dist[start] = 0;
    }

    void dijkstra() {
        while (true) {
            int min_v = -1, min_dist = 1e9;
            for (int i = 0; i < n; i++) {
                if (!used[i] && dist[i] < min_dist) {
                    min_v = i;
                    min_dist = dist[i];
                }
            }
            if (min_v == -1)
                return;
            used[min_v] = true;
            for (int i = 0; i < g[min_v].size(); i++) {
                if (g[min_v][i].a_time < dist[g[min_v][i].dest] && g[min_v][i].d_time >= dist[min_v])
                    dist[g[min_v][i].dest] = g[min_v][i].a_time;
            }
        }
    }

};

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

    Graph graph;
    graph.init(n, start - 1);

    for (int i = 0; i < m; i++) {
        int from, to, old_time, new_time;
        cin >> from >> old_time >> to >> new_time;
        graph.g[from - 1].push_back(Edge(to - 1, old_time, new_time));
    }


    graph.dijkstra();

    if (graph.dist[finish - 1] != 1e9)
        cout << graph.dist[finish - 1];
    else
        cout << -1;


    return 0;
}