Tree - BioHackersNet

TreeGraph. A ConnectedGraph containing no cycles. There is always only one GraphPath from any one node to another.

http://mathworld.wolfram.com/Tree.html

node라는 항목들이 계층적으로 배치되어 구성된 DataStructure.

계층의 가장 상위노드를 루트라고 하고, 바로 아래를 children, 위를 parent라고 한다.

부모가 가질 수 있는 자식노드의 수는 트리의 형태에 따라 다르다. 이것을 분기계수(branching factor)라고 하는데, 이것이 2이면 BinaryTree이다.

My rosland solution

   1 import sys
   2 
   3 nodes = range(1, int(sys.stdin.readline()) + 1)
   4 branches = []
   5 for line in sys.stdin:
   6     a, b = map(int, line.split())
   7     for branch in branches:
   8         if a in branch or (b in branch):
   9             branch.add(a)
  10             branch.add(b)
  11             break
  12     else:
  13         branches.append({a, b})
  14 
  15 singlets = []
  16 for node in nodes:
  17     for branch in branches:
  18         if node in branch:
  19             break
  20     else:
  21         singlets.append(node)
  22 
  23 print 'nodes...', nodes
  24 print 'branches...', branches, len(branches)
  25 print 'singlets...', singlets, len(singlets)
  26 print(len(branches) + len(singlets) - 1)