class GetSuggestedFriends:
    #Constructor, Time O(1) Space O(1)
    def __init__(self) :
        self.adj = {}
        self.groups = []
	
	#Add edges, Time O(1) Space O(1)
    def addFriendship(self, a, b) :    
        if a not in self.adj:
            self.adj[a] = []
        if b not in self.adj:
            self.adj[b] = []   		
        self.adj[a].append(b)
        self.adj[b].append(a)		
	
    # Find groups by connections, DFS, Time O(V+E), Space O(V)
    def findGroups(self) : 
        visited = {}
        for t in self.adj.keys():
            if visited.get(t) == None:
                group = set()
                self.dfs(t, visited, group)
                self.groups.append(group)

	#DFS helper, Time O(V+E), Space O(V) 
    def dfs(self, v, visited, group) :
        visited[v] = True
        group.add(v)
        for ne in self.adj[v] :
            if ne not in visited:
                self.dfs(ne, visited, group)

	#Find suggested friends, Time O(V+E), Space O(V)
    def getSuggestedFriends (self, a) :
        if len(self.groups) == 0:
            self.findGroups()
        res = set()
        for  t in self.groups: 
            if a in t:               
                res = t;             
                break
        if len(res) > 0: #remove himself from suggested friends
            res.remove(a)
        for t in self.adj.get(a):
            res.remove(t)
        return res
		
g = GetSuggestedFriends()
g.addFriendship("Amy", "Chris")
g.addFriendship("Sarah", "Joshua")
g.addFriendship("Joshua", "Zoe")
g.addFriendship("Sarah", "Jess")
g.addFriendship("Amy", "Sam")

name = "Zoe"
print("Suggestion friends of " + name + ": ")
print(g.getSuggestedFriends(name));	

name = "Sam"
print("Suggestion friends of " + name + ": ")
print(g.getSuggestedFriends(name));