트리란 잘 알려진 자료 구조로 공집합 또는 하나 이상의 노드가 방향성 엣지로 연결된 집합을 의미한다.

단, 트리는 다음 조건을 만족한다.

1. 한 노드는 루트라고 하며 루트를 가르키는 엣지는 없다.

2. 나머지 노드들은 그 노드를 가르키는 엣지가 하나씩 있다.

3. 트리의 모든 노드는 루트로부터 그 노드까지 도달하는 유일한 경로가 존재한다.

아래 예를 보자. 원은 노드(node)이고 화살표는 간선(edge)라고 하는데 화살표 방향을 따라 이동이 가능하다.

아래 그림에서 1, 2번은 트리이며 3번 그림은 3번 조건을 만족하지 않으므로 트리가 아니다.

주어진 그래프가 트리인지 확인하는 프로그램을 작성하라.

올바른 트리 timer 1s memory 64MB

올바른 트리 1s 64MB