BOJ 25200 - 곰곰이와 자판기

BOJ 25200 - 곰곰이와 자판기

가장 쉬운 풀이는 특별한 자료구조나 알고리즘없이 $to[i] = i$ 로 모두 초기화하고 $m$개를 뒤부터 보면서 $to[u] = to[v]$ 로 해주는 풀이같다.

왜 이게 되는지 직접 그림을 그려보면서 보면 좋다.

예제의 그림이다.

void solve() {
   int n, m;
   cin >> n >> m;
   vector<pi> a(m);
   vi dp(n, -1);
   for (auto &[u, v]: a) cin >> u >> v, u--, v--;
   for (int i = m - 1; i >= 0; i--) {
      if (dp[a[i].se] == -1) dp[a[i].se] = a[i].se;
      dp[a[i].fi] = dp[a[i].se];
   }
   for (int i = 0; i < n; i++) cout << (dp[i] == -1 ? i + 1 : dp[i] + 1) << ' ';
}