17250번 은하철도

https://www.acmicpc.net/problem/17250

유니온-파인드(union-find) 문제이다.

배열 2개를 활용하면 된다.

주의할 것은 루트 노드가 더 작은 쪽에 더해진다.(sum 배열)

또한, 루트 노드가 같으면 union을 하면 안 된다.

#include <bits/stdc++.h>
 
using namespace std;
 
int n, m;
 
int parent[100100], sum[100100];
 
vector<int> v;
 
int getParent(int x)
{
    if (x == parent[x]) return x;    
    return parent[x] = getParent(parent[x]);
}
 
void unionParent(int a, int b)
{
    a = getParent(a);
    b = getParent(b);
 
    if (a > b) swap(a, b); // 항상 a를 작게
 
    parent[b] = a; // 부모 갱신
    sum[a] += sum[b]; // 루트 노드끼리 더한다. 단, 더 작은 쪽의 루트 노드에 더해진다.
}
 
int main(void)
{
    int f, t;
 
    scanf("%d %d", &n, &m);
    v.resize(n + 1);
 
    for (int i = 0; i < n; i++)
        scanf("%d", &v[i]), parent[i] = i, sum[i] = v[i];
 
    for (int i = 0; i < m; i++)
    {
        scanf("%d %d", &f, &t);
 
        
        if (getParent(f - 1) != getParent(t - 1)) unionParent(f - 1, t - 1); 
        // 이미 루트 노드가 같으면 union을 할 필요 없음.
 
        if (f > t) swap(f, t); // 항상 작은 쪽을 생각한다.
 
        printf("%d\n", sum[getParent(f - 1)]); // 작은 쪽의 루트 노드를 부른다.
    }
 
    return 0;
}