Nik_Perepelov

6 контест Настя

Oct 20th, 2021 (edited)
1,016
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.61 KB | None | 0 0
  1. #include<iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5. vector<int> parents(1000000);
  6. vector<int> weight(1000000);
  7.  
  8. void make_set(int v) {
  9.     parents[v] = v;
  10. }
  11.  
  12. int f_set(int v) {
  13.     if (v == parents[v]) // мы нашли главную вершину
  14.         return v; // возвращаем её
  15.     return parents[v] = f_set(parents[v]); // обращаемся к родителю за галвной вершиной и сжимаем путь
  16. }
  17.  
  18. void u_sets(int a, int b, int c) {
  19.     a = f_set(a); // находим главную вершину первой компоненты
  20.     b = f_set(b); // находим главную вершину второй компоненты
  21.     if (a != b) { // проверяем, разыные ли компоненты соединяет ребро
  22.         // да
  23.         weight[a] += weight[b]; // складываем веса компонент
  24.         parents[b] = a; // переназначаем главную вершину
  25.     }
  26.     // в любом случае делаем
  27.     weight[a] += c; // добавляем вес ребра
  28. }
  29.  
  30. int main() {
  31.     int n, m, inp, x, y, z;
  32.     cin >> n >> m;
  33.     for (int i = 0; i < n; i++)
  34.         make_set(i);
  35.     for (int i = 0; i < m; i++) {
  36.         cin >> inp;
  37.         if (inp == 1) {
  38.             cin >> x >> y >> z;
  39.             u_sets(x - 1, y - 1, z); // соденияем разыне компоненты
  40.         } else {
  41.             cin >> x;
  42.             cout << weight[f_set(x - 1)] << endl; // узнаем вес компоненты из главной вершины
  43.         }
  44.     }
  45. }
Add Comment
Please, Sign In to add comment