친구 네트워크

[python3] 백준 4195 (친구 네트워크, 유니온 파인드)

문제는 아주 심플하다. 소셜네트워크를 구성할때 서로 친구가 될때마다 해당 네트워크에 몇명이 속하는지 알아내면 된다. 테스트 케이스의 범위는 주어지지 않았지만 F의 값이 100,000으로 주어졌다. 그럼 테스트 케이스 * 100,000으로 상당히 연산량이 클것으로 예상된다. 또한 DFS를 통해 구성된 네트워크의 노드 갯수를 센다고 가정한다면 100,000 * O(N) 정도의 시간 복잡도가 걸리는데 만약 N이 100,000이 된다면 너무 시간복잡도가 크다. 즉, 매번 탐색하는 방식으로는 구할 수가 없다. 그럼 A라는 친구가 어디 네트워크에 속하고, 네트워크의 크기는 어느정도인지 한번에 안다면 우리는 testcase*100,000의 연산만으로 정답을 구할 수 있다. 딱 냄새가 난다 네트워크에 속하고 머시기 어..