問題
트리란 잘 알려진 자료 구조로 공집합 또는 하나 이상의 노드가 방향성 엣지로 연결된 집합을 의미한다.
단, 트리는 다음 조건을 만족한다.
1. 한 노드는 루트라고 하며 루트를 가르키는 엣지는 없다.
2. 나머지 노드들은 그 노드를 가르키는 엣지가 하나씩 있다.
3. 트리의 모든 노드는 루트로부터 그 노드까지 도달하는 유일한 경로가 존재한다.
아래 예를 보자. 원은 노드(node)이고 화살표는 간선(edge)라고 하는데 화살표 방향을 따라 이동이 가능하다.
아래 그림에서 1, 2번은 트리이며 3번 그림은 3번 조건을 만족하지 않으므로 트리가 아니다.
주어진 그래프가 트리인지 확인하는 프로그램을 작성하라.
入力
입력은 여러 케이스로 구성된다. 입력의 끝은 음의 정수 두 개로 나타난다. 각 테스트 케이스의 끝은 0의 쌍으로 나타난다. 각 한 쌍의 정수는 엣지를 의미한다. 두 정수 중 먼저 나타나는 수로부터 두 번째 수를 가르키는 엣지가 존재한다는 뜻이다.
각 테스트 케이스의 입력되는 간선의 총수는 100000개를 넘지 않는다. 노드 번호는 1이상 10억 이내의 정수이다.出力
각 입력의 그래프가 트리라면 "Case k is a tree." 그렇지 않다면 "Case k is not a tree." 여기서 k는 테스트 케이스 번호를 의미한다.
例題
6 8 5 3 5 2 6 4
5 6 0 0
8 1 7 3 6 2 8 9 7 5
7 4 7 8 7 6 0 0
3 8 6 8 6 4
5 3 5 6 5 2 0 0
-1 -1
Case 1 is a tree.
Case 2 is a tree.
Case 3 is not a tree.
出典
NCNA 1997 2
ログインしないとコードを書けません。