Прикреплённый файл «Tkachenko_Mexico(DFS).py»

Загрузка

   1 c=input()
   2 n=input()
   3 a=[[0 for i in xrange(c)] for j in xrange(c)]
   4 x, y=0, 0
   5 for i in xrange(n):
   6     x, y=raw_input().split()
   7     x, y=int(x), int(y)
   8     a[x-1][y-1]=1
   9     a[y-1][x-1]=1
  10 
  11 used=[0 for i in xrange(c)]
  12 res=[]
  13 
  14 def check(k, l):
  15     if(abs(k-l)==1):
  16         return 1
  17     k, l=min(k, l), max(k, l)
  18     if(k==0)and(l==c-1):
  19         return 1
  20     t=used[k+1]
  21     for i in xrange(k+1, l):
  22         if used[i]!=t:
  23             return 0
  24     if t==0:
  25         t=1
  26     else:
  27         t=0
  28     for i in xrange(0, k):
  29         if used[i]!=t:
  30             return 0
  31     for i in xrange(l+1, c):
  32         if used[i]!=t:
  33             return 0
  34     return 1
  35     
  36 
  37 def dfs(k):
  38     res.append(k+1)
  39     used[k]=1
  40     t=0
  41     for i in xrange(c):
  42         if(used[i]==0)and a[i][k]==1 and check(i, k)==1:
  43             t=1
  44             dfs(i)
  45         if(t==0)and i==c-1 and len(res)!=c:
  46             res.pop()
  47             
  48 t=0      
  49 for i in xrange(c):
  50     res=[]
  51     used=[0 for j in xrange(c)]
  52     dfs(i)
  53     if(len(res)==c):
  54         t=1
  55         for j in xrange(c):
  56             print str(res[j])
  57         break
  58 if(t!=1):
  59     print -1

Прикреплённые файлы

Для ссылки на прикреплённый файл в тексте страницы напишите attachment:имяфайла, как показано ниже в списке файлов. Не используйте URL из ссылки «[получить]», так как он чисто внутренний и может измениться.

Вам нельзя прикреплять файлы к этой странице.