Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include <vector>
- using namespace std;
- vector<int> parents(1000000);
- vector<int> weight(1000000);
- void make_set(int v) {
- parents[v] = v;
- }
- int f_set(int v) {
- if (v == parents[v]) // мы нашли главную вершину
- return v; // возвращаем её
- return parents[v] = f_set(parents[v]); // обращаемся к родителю за галвной вершиной и сжимаем путь
- }
- void u_sets(int a, int b, int c) {
- a = f_set(a); // находим главную вершину первой компоненты
- b = f_set(b); // находим главную вершину второй компоненты
- if (a != b) { // проверяем, разыные ли компоненты соединяет ребро
- // да
- weight[a] += weight[b]; // складываем веса компонент
- parents[b] = a; // переназначаем главную вершину
- }
- // в любом случае делаем
- weight[a] += c; // добавляем вес ребра
- }
- int main() {
- int n, m, inp, x, y, z;
- cin >> n >> m;
- for (int i = 0; i < n; i++)
- make_set(i);
- for (int i = 0; i < m; i++) {
- cin >> inp;
- if (inp == 1) {
- cin >> x >> y >> z;
- u_sets(x - 1, y - 1, z); // соденияем разыне компоненты
- } else {
- cin >> x;
- cout << weight[f_set(x - 1)] << endl; // узнаем вес компоненты из главной вершины
- }
- }
- }
Add Comment
Please, Sign In to add comment