Untitled
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...