Прикреплённый файл «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 из ссылки «[получить]», так как он чисто внутренний и может измениться.- [получить | показать] (2011-09-26 11:35:41, 1.1 KB) [[attachment:Sav_circled.py]]
- [получить | показать] (2011-09-26 11:35:41, 0.7 KB) [[attachment:Sav_cities.py]]
- [получить | показать] (2011-09-26 11:35:41, 1.1 KB) [[attachment:Tkachenko_Mexico(DFS).py]]
Вам нельзя прикреплять файлы к этой странице.