백준#4195 친구 네트워크

1. 문제

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

  • Medium / 해시,집합,그래프 / 50분 컷

2. 나의 풀이

문제부터가 이해가 안된다...
문제 이했음!
생각보다 간단해서....... 왜 어려워했는가... 그랬음

A와 B의 모든 친구의 수(중복 허용x)를 구하는 문제

답은 구해지는데 시간초과ㅠ.ㅠ

import sys


case_count = int(sys.stdin.readline().rstrip())

for c in range(case_count):
    network_count = int(sys.stdin.readline().rstrip())
    networks = {}
    for n in range(network_count):
        a, b = sys.stdin.readline().split()
        a_group = networks.get(a) if networks.get(a) else [a, b]
        b_group = networks.get(b) if networks.get(b) else [b, a]
        new_group = list(set(a_group + b_group))

        networks[a] = new_group
        networks[b] = new_group
        print(len(new_group))

3. 남의 풀이

def find(x):
    if x == parent[x]:
        return x
    else:
        p = find(parent[x])
        parent[x] = p
        return parent[x]


def union(x, y):
    x = find(x)
    y = find(y)

    if x != y:
        parent[y] = x
        number[x] += number[y]


test_case = int(input())

for _ in range(test_case):
    parent = dict()
    number = dict()

    f = int(input())

    for _ in range(f):
        x, y = input().split(' ')

        if x not in parent:
            parent[x] = x
            number[x] = 1
        if y not in parent:
            parent[y] = y
            number[y] = 1

        union(x, y)
        print(number[find(x)])

4. 느낀 점

좋은 웹페이지 즐겨찾기