SHARE
TWEET

Untitled

a guest Oct 20th, 2019 125 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. from collections import defaultdict
  2. import random
  3.  
  4.  
  5. def programming_team_selection():
  6.     while True:
  7.         n_pairs = int(input())
  8.         if n_pairs == 0:
  9.             return
  10.         adj_list = defaultdict(lambda: [])
  11.         for i in range(n_pairs):
  12.             s1, s2 = input().split()
  13.             adj_list[pair[0]].append(s1)
  14.             adj_list[pair[1]].append(s2)
  15.         if clique_thing(adj_list):
  16.             print("possible")
  17.         else:
  18.             print("impossible")
  19.  
  20.  
  21. def find_teamless(has_team):
  22.     keys = list(has_team.keys())
  23.     random.shuffle(keys)
  24.     for key in keys:
  25.         if has_team[key] == False:
  26.             return key
  27.     return None
  28.  
  29.  
  30. def clique_thing(adj_list):
  31.     #def print(x):
  32.     #    pass
  33.     #print("====== New Test Case ======")
  34.     #print(adj_list)
  35.     def local_recurrer(used, teams):
  36.         #print("Recursion with:")
  37.         #print(used)
  38.         #print(teams)
  39.         # find first unused guy, he's the team captain ;)
  40.         captain = find_teamless(used)
  41.         # if there isn't one, everyone has a clique and we're happy
  42.         if captain is None:
  43.             return True
  44.         used[captain] = True
  45.         #print(f"The captain is {captain}")
  46.  
  47.         # otherwise we have to fill the team
  48.         for lieutenant in adj_list[captain]:
  49.             if used[lieutenant]:
  50.                 continue
  51.             used[lieutenant] = True
  52.             # ok, we have a possible second guy
  53.             for third_guy in adj_list[captain]:
  54.                 if used[third_guy] or third_guy not in adj_list[lieutenant]:
  55.                     continue
  56.                 used[third_guy] = True
  57.                 # and a possible third guy
  58.                 teams.append([captain, lieutenant, third_guy])
  59.                 if local_recurrer(used, teams):
  60.                     return True
  61.                 used[third_guy] = False
  62.                 teams.remove([captain, lieutenant, third_guy])
  63.             used[lieutenant] = False
  64.         #print("Got stuck!")
  65.         used[captain] = False
  66.         return False
  67.  
  68.     teams = []
  69.     used = {name: False for name in adj_list.keys()}
  70.     result = local_recurrer(used, teams)
  71.     if result:
  72.         print(teams)
  73.         return teams
  74.     else:
  75.         return None
  76.  
  77.  
  78. def main():
  79.     programming_team_selection()
  80.  
  81.  
  82. if __name__ == '__main__':
  83.     main()
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top