문제: www.acmicpc.net/problem/17831 17831번: 대기업 승범이네 첫 번째 줄에 판매원들의 수 N(2 ≤ N ≤ 200,000)이 주어진다. 판매원들은 1번, 2번, …, N번으로 번호가 매겨지며, 승범이는 항상 1번이다. 두 번째 줄에 2번 판매원부터 N번 판매원의 사수가 순서대 www.acmicpc.net ​ N명의 직원이 사수와 부사수 관계가 배정된다. 그런데 모든 직원에게는 사수가 한 명씩만 배정된다고 했으므로 N명의 직원을 정점으로 고려할 때 그래프는 트리 형태를 지님을 알 수 있다. 사장 승범이인 root 정점을 제외한 직원 정점은 오직 하나의 부모 정점만 갖게 되고, 이는 임의의 서로 다른 두 정점 사이의 경로는 하나밖에 없음이 보장되기 때문이다. ​ 사수와 부사수 ..

BOJ 백준 3770 대한민국 문제:www.acmicpc.net/problem/3770 3770번: 대한민국 입력의 첫째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 N, M, K가 주어진다. K는 고속도로의 수이다. 둘째 줄부터 K개의 줄에는 고속도로의 정보가 주어진다. 고 www.acmicpc.net ​ 대한민국의 동해안 도시와 서해안 도시가 각각 N개, M개 있고, 동해안과 서해안을 연결하는 고속도로가 K개 있을 때 고속도로가 서로 교차하는 곳의 개수를 구하는 문제이다. 단, 한 점에 교차하는 고속도로의 개수는 2개이다. ​ 고속도로의 개수인 K의 제한이 40만이므로 시간 복잡도로 인해 단순히 loop를 두 번 시행함으로써 계산할 수 있는 문제는 아니다. ​ 이 문제..