-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path0520_huawei_2.py
More file actions
49 lines (42 loc) · 1.31 KB
/
0520_huawei_2.py
File metadata and controls
49 lines (42 loc) · 1.31 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
# input is "A->B;B->D;C->B;C->E;D->C"
# process input, form a matrix grid (graph)
import pdb
def main():
in_str = input()
edges = in_str.split(";")
graph = [[0] * 10 for _ in range(10)] # 10*10 matrix
for e in edges:
s, t = ord(e[0])-ord("A"), ord(e[-1])-ord("A")
graph[s][t] = 1
# dfs the graph
visited = [False] * 10
res = []
def dfs(graph, i, path):
# path is str recording the traverse route
visited[i] = True
for j in range(10):
if graph[i][j] != 0:
if not visited[j]:
dfs(graph, j, path+chr(ord("A") + j))
visited[j] = False
elif visited[j]:
res.append(path)
return
""" ! need compute the in-degree, then dfs all the 1-in-degree nodes """
start = ord(in_str[0]) - ord('A')
# need to dfs all the node, whose indegree==0
dfs(graph, start, "")
if res:
string = res[0]
minnode = string[0]
minid = 0
for i in range(len(string)):
if string[i] < minnode:
minnode = string[i]
minid = i
p_res = string + string
print(p_res[minid: (minid + len(string))])
else:
print("-")
if __name__ == '__main__':
main()