How to find friends
1916 ワード
How to find friends
考え方が簡単で,符号化が容易ではない 1 def check_connection(network, first, second):
2 link_dictionary = dict() 3 4 for link in network: 5 drones = link.split('-') 6 7 link_dictionary.setdefault(drones[0], []).append(drones[1]) 8 link_dictionary.setdefault(drones[1], []).append(drones[0]) 9 10 future = [] 11 visited = [] 12 future.append(first) 13 14 while future: 15 current = future.pop() 16 visited.append(current) 17 18 extend = link_dictionary[current] 19 20 if second in extend: 21 return True 22 23 for each in extend: 24 if each not in visited: 25 future.append(each) 26 27 return False
dictを使用して、{lyly:[lala,gege]}などの各人の直接関係を格納します.2つのlistを使用します.1つは遍歴した人を表し、もう1つは遍歴する人を表します.
さらにpythonの2次元配列は、connection=[[False for col in range(5)]for row in range(5)]という5*5の配列を定義することができ、error=[[False]*5]*5という定義を試みたが、修正すれば
error[0][0]、ではerror[1][0]、error[2][0]...いずれも修正するが、[False]*5は1次元配列を生成し、外側の*5は5つの参照を生成するだけであるため、いずれを修正しても残りは変更される.
大神のコードを観覧します 1 def check_connection(network, first, second):
2 setlist = [] 3 for connection in network: 4 s = ab = set(connection.split('-')) 5 # unify all set related to a, b 6 for t in setlist[:]: # we need to use copy 7 if t & ab: # check t include a, b 8 s |= t 9 setlist.remove(t) 10 setlist.append(s) # only s include a, b 11 12 return any(set([first, second]) <= s for s in setlist)
各関係をsetとし、関係間の交差が空でなければ、関係間の並列、すなわち関係輪を求める.
最後にfirstとsecondが関係圏にあるかどうかを確認します.
setの操作,&交,|並,<=サブセットを十分に利用した.
12行目の文法特性もあります
1 def check_connection(network, first, second):
2 link_dictionary = dict() 3 4 for link in network: 5 drones = link.split('-') 6 7 link_dictionary.setdefault(drones[0], []).append(drones[1]) 8 link_dictionary.setdefault(drones[1], []).append(drones[0]) 9 10 future = [] 11 visited = [] 12 future.append(first) 13 14 while future: 15 current = future.pop() 16 visited.append(current) 17 18 extend = link_dictionary[current] 19 20 if second in extend: 21 return True 22 23 for each in extend: 24 if each not in visited: 25 future.append(each) 26 27 return False
1 def check_connection(network, first, second):
2 setlist = [] 3 for connection in network: 4 s = ab = set(connection.split('-')) 5 # unify all set related to a, b 6 for t in setlist[:]: # we need to use copy 7 if t & ab: # check t include a, b 8 s |= t 9 setlist.remove(t) 10 setlist.append(s) # only s include a, b 11 12 return any(set([first, second]) <= s for s in setlist)