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行目の文法特性もあります