BOJ [트리인가?]

문제

2022-03-31

위와 같은 그래프가 주어졌을 때 해당 그래프가 트리인지 판별하는 문제

입력은 다음과 같이 주어진다.

코드

dict.values() 하면 value들이 하나의 list로 주어지는 것이 아니라

이중 list로 주어진다는 사실을 몰라서 헤맸다.

주의할것!!!

---

from collections import defaultdict, deque

count = 1

while True:
  
  arr = []
  isEnd = False
  while True:
    arr += (list(input().split("  ")))  
    if arr[-1] == "0 0":
      break
    if arr[-1] == "-1 -1":
        isEnd = True
        break
        
  if isEnd:
    break
  
  for i in range(len(arr)):
    arr[i] = list(map(int,arr[i].split()))

  del arr[-1]

  tree_dict = defaultdict(list)
  
  for i in arr:
    tree_dict[i[0]].append(i[1])

  start = 0
  visited = {}

  for key in tree_dict.keys():
    isStart = True
    for value in tree_dict.values():
      if key in value:
        isStart = False
    if isStart:
      start = key

  for values in tree_dict.values():
    for value in values:
      visited[value] = False    
  
  isTree = True
  
  def bfs(tree_dict, start):

    global isTree
    global visited
    
    q = deque([])
    q.append(start)

    while q:
      
      now = q.popleft()
      for i in tree_dict[now]:
        if visited[i]:
          
          isTree = False
          break
        else:
          visited[i] = True
          q.append(i)
  
  bfs(tree_dict, start)

 
  
  if False in visited.values():
    isTree = False

  if isTree:
    print("Case " + str(count) + " is a tree.")
  else:
    print("Case " + str(count) + " is not a tree.")

  count += 1
  
  n = input();
  if n == "-1 -1":
    break