прикреплённый файл:content.py к странице LecturesVMSH/2010-12-08

   1 #!/usr/bin/python
   2 # coding: utf-8
   3 '''
   4 Вводится список вида
   5 
   6   Мука      Хлеб
   7   Соль      Хлеб
   8   Вода      Хлеб
   9   Хлеб      Бутерброд
  10   Масло     Бутерброд
  11   Сыр       Бутерброд
  12   Бутерброд Завтрак
  13   Чай       Завтрак
  14   ...
  15 описывающий, как нечто собирается из составных частей.
  16    1. Ввести название и вывести его неделимые составные части (для Бутерброда это будут Мука Соль Вода Масло Сыр).
  17    2. Проверить правильность списка (не изготавливается ли предмет в конечном итоге сам из себя)
  18 '''
  19 
  20 import sys, copy
  21 
  22 def Input(f):
  23     Cont={}
  24     for l in f.xreadlines():
  25          s=l.split()
  26          if len(s)>1:
  27              Cont.setdefault(s[1],set([])).add(s[0])
  28          else:
  29              return Cont,l.strip()
  30 
  31 def Output(d):
  32     for k,v in d.items():
  33         print k,":"," ".join(v)
  34 
  35 Cont,Word=Input(sys.stdin)
  36 # Проверить правильность списка 
  37 # (не изготавливается ли предмет в конечном итоге сам из себя) 
  38 Check=copy.deepcopy(Cont)   # Не будем портить исходный словарь
  39 for i in Check:             # Это просто len(Check) шагов
  40     for k in Check:         # Добавим все детали деталей
  41         Check[k]|=set([e for j in Check[k] if j in Check for e in Check[j]])
  42         if k in Check[k]:
  43             print "Ошибка: {0} зависит от {0}".format(k)
  44             sys.exit(1)
  45 
  46 # вывести его неделимые составные части
  47 WCont,OCont=Cont[Word].copy(),set([])
  48 while WCont != OCont:
  49     OCont,WCont=WCont,set([])
  50     for e in OCont:
  51         if e in Cont:
  52             WCont.update(Cont[e])
  53         else:
  54             WCont.add(e)
  55 print Word, ":", " ".join(WCont)