Untitled

 avatar
unknown
plain_text
2 years ago
1.5 kB
3
Indexable
#include <iostream>

using namespace std;

#define MAX 100001

int set[MAX];
int number_elem_og[MAX];
int number_elem[MAX];
int aux;

int findset(int val) {
    if (set[val] == val) 
        return val;
    return set[val] = findset(set[val]);
}

bool unionset(int i, int j) {
    int a = findset(i);
    int b = findset(j);
    if (a == b) 
        return false;
    set[b] = a;
    number_elem_og[a] += number_elem_og[b];
    number_elem[a] += number_elem[b];
    if (aux == b)
        aux = a;
}

int main() {
    int n, m;
    int i;
    while(scanf("%d %d", &n, &m), n|m) {
        int ans = 0;
        aux = 1;
        for(i = 1; i <= n; i++) {
            scanf("%d", number_elem_og+i);            
            set[i] = i;
            number_elem[i] = 0;
        }

        for(i = 0; i < m; i++) {
            int q, a, b;
            scanf("%d %d %d", &q, &a, &b);
            
            if (q==1) {
                unionset(a, b);
            }
            if (q==2) {
                int parent_a = findset(a);
                int parent_b = findset(b);
                if (number_elem_og[parent_a] > number_elem_og[parent_b]) {
                    number_elem[parent_a]++;
                    if (aux == parent_a)
                        ans++;
                }
                if (number_elem_og[parent_a] < number_elem_og[parent_b]) {
                    number_elem[parent_b]++;
                    if (aux == parent_b) 
                        ans++;
                }
            }
        }
        printf("%d\n", ans);
    }
}
Editor is loading...