Ярику доп контест

/* 1 таск */

#include <iostream>
#include <vector>

using namespace std;

class Graph {

    vector<int> parent;
    vector<vector<int>> cats;
    vector<int> size;

public:

    explicit Graph(int n) {
        parent.resize(n);
        cats.resize(n);
        size.resize(n, 1);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            cats[i].push_back(i);
        }
    }

    int getParent(int v) {
        if (parent[v] == v) {
            return v;
        }
        return parent[v] = getParent(parent[v]);
    }
    void joinSets(int set1, int set2) {
        set1 = getParent(set1);
        set2 = getParent(set2);
        if (set1 != set2) {
            if (size[set1] < size[set2])
                swap(set1, set2);
            cats[set1].insert(cats[set1].end(), cats[set2].begin(), cats[set2].end());
            cats[set2].clear();
            parent[set2] = set1;
            size[set1] += size[set2];
        }
    }

    void catPr() {
        int main_cat = getParent(0);
        for (int i : cats[main_cat]) {
            cout << i + 1 << ' ';
        }
    }
};



int main() {
    int n;
    cin >> n;
    Graph dsu(n);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        dsu.joinSets(a - 1, b - 1);
    }
    dsu.catPr();

    return 0;
}

/* 2 таск */

#include <iostream>
#include <vector>

using namespace std;

class DSU {

    int number_of_sets;
    vector<int> parent;

public:

   DSU(int n) {
        number_of_sets = n;
        parent.resize(n);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

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

    void join_sets(int set1, int set2) {
        set1 = get_parent(set1);
        set2 = get_parent(set2);
        if (set1 != set2) {
            parent[set2] = set1;
            number_of_sets--;
        }
    }

    int get_number_of_sets() const {
        return number_of_sets;
    }
};



int main() {
    int n, m, k;
    cin >> n >> m >> k;
    DSU dsu(n);
    vector<int> type(k);
    vector<int> from(k);
    vector<int> to(k);
    for (int i = 0; i < m; i++) {
        int trash;
        cin >> trash >> trash;
    }
    for (int i = 0; i < k; i++) {
        string input_type;
        int a, b;
        cin >> input_type >> a >> b;
        if (input_type == "ask")
            type[i] = 1;
        else
            type[i] = 2;
        from[i] = a - 1;
        to[i] = b - 1;
    }

    vector<bool> ans;
    for (int i = k - 1; i >= 0; i--) {
        if (type[i] == 2) {
            dsu.join_sets(from[i], to[i]);
        } else {
            ans.push_back(dsu.get_parent(from[i]) == dsu.get_parent(to[i]));

        }
    }

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

    return 0;
}

/* 3 таск */

#include <iostream>
#include <vector>

using namespace std;

class Graph {
    int n;
    vector<vector<int>> gкфзр;
    vector<int> answer;
    vector<int> used;
public:
    Graph(int _n, vector<vector<int>> &_g) {
        n = _n;

        used.resize(n);
        gкфзр = _g;
    }

    void dfs(int v, int parent) {
        used[v] = 1;
        for (auto &i: gкфзр[v]) {
            if (used[i] == 1) {
                cout << "No";
                exit(0);
            }
            if (used[i] == 0) {
                dfs(i, v);
            }
        }
        used[v] = 2;
        answer.push_back(v);
    }

    void solve() {
        for (int i = 0; i < n; i++) {
            if (!used[i]) {
                dfs(i, -1);
            }
        }
    }

    void print_answer() {
        cout << "Yes" << endl;
        for (int i = 0; i < n; i++) {
            cout << answer[n - 1 - i] + 1 << ' ';
        }
    }
};


int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> input_graph;

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        input_graph[a].emplace_back(b);
    }

    Graph g(n, input_graph);
    g.solve();
    g.print_answer();


    return 0;
}

/* 4 таск на основе класса из 2 таска */


int main() {
    int n;
    cin >> n;
    DSU dsu(n);
    for (int i = 0; i < n; i++) {
        int inp;
        cin >> inp;
        inp--;
        dsu.join_sets(i, inp);
    }
    cout << dsu.get_number_of_sets();

    return 0;
}

/* 7 таск */

//
//  main.cpp
//  zadacha
//
//  Created by Yaroslav Monastyrev on 24.10.2021.
//

#include <iostream>
#include <vector>

struct Edge {
    int destination;
    int departing_time;
    int arrival_time;

    Edge() {
        destination = 0;
        departing_time = 0;
        arrival_time = 0;
    }

    Edge(int _to, int _departing_time, int _arrival_time) {
        destination = _to;
        departing_time = _departing_time;
        arrival_time = _arrival_time;
    }
};

using namespace std;

class Graph {

    int n;
    int start;
    int finish;
    vector<int> used;
    vector<vector<Edge>> g;
    vector<int> dist_time;

public:

    Graph(int _n, int _start, int _finish) {
        n = _n;
        start = _start;
        finish = _finish;

        g.resize(n);
        used.resize(n);
        dist_time.resize(n, 1e9);
        dist_time[start] = 0;
    }

    void set_graph(vector<vector<Edge>> &_g) {
        g = _g;
    }

    void dijkstra() {
        for (;;) {
            int minimal_station = -1;
            int minimal_time = 1e9;
            for (int i = 0; i < n; i++) {
                if (!used[i] && dist_time[i] < minimal_time) {
                    minimal_time = dist_time[i];
                    minimal_station = i;
                }
            }
            if (minimal_station == -1)
                return;
            used[minimal_station] = true;
            for (auto &i: g[minimal_station]) {
                if (i.departing_time >= dist_time[minimal_station] && i.arrival_time < dist_time[i.destination])
                    dist_time[i.destination] = i.arrival_time;
            }
        }
    }

    int get_answer() {
        if (dist_time[finish] != 1e9)
            return dist_time[finish];
        return -1;
    }

};


int main() {
    int n, e, m;
    cin >> n >> e >> m;
    vector<vector<Edge>> input_graph(n);
    for (int i = 0; i < m; i++) {
        int k;
        cin >> k;
        int from, to, old_time, time;
        for (int j = 0; j < k; j++) {
            cin >> to >> time;
            to--;
            if (j > 0) {
                input_graph[from].emplace_back(to, old_time, time);
            }
            from = to;
            old_time = time;
        }
    }

    Graph g(n, 0, e - 1);
    g.set_graph(input_graph);
    g.dijkstra();
    cout << g.get_answer();
}

/* 8 таск. Меняется только main*/

int main() {
    int n, r, d, v;
    cin >> n >> d >> v >> r;
    vector<vector<Edge>> input_graph(n);
    for (int i = 0; i < r; i++) {
        int from, departing_time_curr, to, arrival_time_curr;
        cin >> from >> departing_time_curr >> to >> arrival_time_curr;
        from--;
        to--;
        input_graph[from].emplace_back(to, departing_time_curr, arrival_time_curr);
    }

    Graph g(n, d - 1, v - 1);
    g.set_graph(input_graph);
    g.dijkstra();
    cout << g.get_answer();
}