문제

링크
https://www.acmicpc.net/problem/4195\

풀이

기본 유니온 파인드 자료구조를 사용하면 되는 문제이다 하지만 이 문제에서는
집합의 이름이 숫자가 아닌 string형태이므로 이점을 유의해서 구현 해야되었고
따라서 parent 공간을 리스트가아닌 string의 형태로 인덱싱 할 수 있는 딕셔너리 자료형으로
구현했다.

코드

import sys
input = sys.stdin.readline

def find_parent(parent, x):
  if x != parent[x]:
    parent[x] = find_parent(parent, parent[x])
    return parent[x]
  return x

def union_parent(parent, a, b):
  a = find_parent(parent, a)
  b = find_parent(parent, b)

  if a != b:
    parent[a] = b
    number[b] += number[a]
    
T = int(input().rstrip())
for _ in range(T):
  parent = dict()
  number = dict()
  F = int(input().rstrip())
  for _ in range(F):
    name1, name2 = input().split()

    if name1 not in parent:
      parent[name1] = name1
      number[name1] = 1
    if name2 not in parent:
      parent[name2] = name2
      number[name2] = 1
      
    union_parent(parent, name1, name2)
    print(number[find_parent(parent, name1)])

다른사람의 코드를 보고난후

사실 파이썬은 대부분 이런식으로 구현했다.
따라서 다음 질문이 중요하다.

딕셔너리 자료형을 쓰지 않았다면...??

c++에서는
map 함수를 통해 <string, int>를 통해서 딕셔너리 자료형을 대체했다.
따라서 큰틀에서는 똑같이 해결할 수 있는 문제이다.
map함수와 딕셔너리 자료형이 어는정도 일대일 대응되는 느낌이다.