백준 알고리즘 17250번 : 은하철도

링크

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

sol1) 유니온 파인드

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define int int64_t
using namespace std;

int n,m; 
int v[100001];

struct UnionFind {
	vector<int> parent, rank, cnt;
	UnionFind(int n) : parent(n), rank(n, 1), cnt(n, 1) {
		iota(parent.begin(), parent.end(), 0);
	}
	int Find(int x) {
		return x == parent[x] ? x : parent[x] = Find(parent[x]);
	}
	bool Union(int a, int b) {
		a = Find(a), b = Find(b);
		if (a == b) return 0;
		if (rank[a] < rank[b]) swap(a, b);
		parent[b] = a;
		rank[a] += rank[a] == rank[b];
		cnt[a] += cnt[b];
    	v[a] += v[b];
		return 1;
	}
};

int32_t main(){
  fastio;
  cin >> n >> m;
  UnionFind UF(n + 1);
  for(int i = 1; i <= n; i++) cin >> v[i];
  while(m--){
    int a,b; cin >> a >> b;
    UF.Union(a, b);
    cout << v[UF.Find(a)] << "\n";
  }
}

배열에 각 정점들이 가지고 있는 행성을 넣어놓고 입력을 받으면서 합칠 때마다 부모노드에 자식 노드의 행성의 개수를 더해줍니다.
행성의 개수를 출력할 때는 루트 노드의 행성의 개수를 출력해주면 됩니다.