[대표 유형] 그래프 탐색

문제 설명

정점의 개수 n, 양방향 간선 정보가 담긴 edges가 매개 변수로 주어질 때 1번 정점을 포함해 1번 정점에서부터 도달할 수 있는 모든 정점의 개수를 반환하는 solution 함수를 작성하시오.

예를 들어, 아래와 같이 6개의 정점과 5개의 간선으로 이루어진 그래프가 있다고 가정합니다.

1번 정점을 출발 정점으로 하여 그래프를 탐색하면, 1번을 포함하여 2, 3, 4, 5번 정점에 방문할 수 있으므로 5를 반환합니다.

제한 사항

• 정점의 개수 n은 2 이상 10,000 이하의 자연수입니다.
• 양방향 간선 정보 edges의 원소는 특정 간선의 양 끝 정점의 정점 번호 x, y로 이루어집니다.
  • edges는 최대 1,000,000개의 간선 정보를 가집니다.
  • x, y는 1 이상 n 이하의 자연수입니다.

예시 테스트케이스 설명

1번 테스트케이스 설명

• 1번 정점에서 출발하여 도달할 수 있는 모든 정점의 번호는 {1, 2, 3, 4, 5}번 정점입니다.

2번 테스트케이스 설명

• 1번 정점에서 출발하여 도달할 수 있는 모든 정점의 번호는 {1, 2, 3, 4, 5, 6, 7, 8}번 정점입니다.

3번 테스트케이스 설명

• 1번 정점에서 출발하여 도달할 수 있는 모든 정점의 번호는 {1, 2}번 정점입니다.

참고 내용

• python 개발 환경에서 17, 19, 20번 등의 테스트케이스에서 에러(런타임 에러) 가 발생한 경우 다음 내용을 참고하시오.
  • python은 재귀함수의 최대 호출 깊이를 1,000으로 제한하고 있습니다.
  • 이에 재귀 함수를 너무 깊게 호출한다면 런타임 에러의 일종인 Recursionerror를 발생시킵니다.
  • python에서 재귀함수의 최대 호출 깊이를 조정하기 위해서는 아래 예시와 같이 코드를 작성하여야 합니다.

import sys
sys.setrecursionlimit(10**6)
 
def solution(n, edges):
  return 0