[백준] 7511 소셜 네트워킹 어플리케이션 python

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

7511번: 소셜 네트워킹 어플리케이션

floyd warshall을 사용해야할까 생각했는데 값이 너무 많아서 다른 방법인 union find로 풀었다.

알고리즘 자체는 어렵지 않았지만 꽤 많이 틀린 문제였다.

union-find를 구현하면서 생각보다 많이 틀렸는데 find를 할때마다 값을 갱신하는게 꼭 필요했다.

그 외엔 TC 변수를 i로 둬서 root = [i for i in range(n)] 이랑 겹쳐 틀렸다는거...(이것도 찾는게 오래걸렸다)

# import sys; input = sys.stdin.readline
def find(a, root):
    if root[a] == a:
        return a
    root[a] = find(root[a], root)
    return root[a]


def union(a, b, root):
    x = find(a, root)
    y = find(b, root)
    if x == y:
        return
    root[y] = x
    return


def main():
    answer = []
    for tc in range(int(input())):
        answer.append("Scenario {}:\n".format(tc + 1))
        n = int(input())
        k = int(input())
        root = [i for i in range(n)]
        for _ in range(k):
            a, b = map(int, input().split())
            union(a, b, root)

        m = int(input())
        for _ in range(m):
            u, v = map(int, input().split())
            ru, rv = find(u, root), find(v, root)
            if ru == rv:
                answer.append('1\n')
            else:
                answer.append('0\n')
        answer.append('\n')
    print(''.join(answer))

if __name__ == '__main__':
    main()

 

rank를 사용해서 트리를 적당히 분배하면 속도 개선도 가능할거같다.