[백준] 7511번 - 소셜 네트워킹 어플리케이션 (C++) 문제 및 풀이

문제) 백준 - 분리 집합 - 소셜 네트워킹 어플리케이션

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

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

 

친구 두 명이 주어질 때, 서로 친구인지 확인해야 됩니다. 쿼리 최대 개수가 10만이기에 각 쿼리를 O(1)의 시간 복잡도로 해결할 수 있는 분리 집합(Union-Find)을 활용하여 해결했습니다. Merge(Union)와 Find는 O(N)이므로 N이 100만이여도 해결할 수 있습니다. 

 

C++ 소스코드)

 

 

Full Code)

https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%205000~9999/7511_%EC%86%8C%EC%85%9C%20%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%82%B9%20%EC%96%B4%ED%94%8C%EB%A6%AC%EC%BC%80%EC%9D%B4%EC%85%98.cpp

GitHub - Chocochip101/BOJ_Solution: BOJ Solutions