Given the array favoriteCompanies where favoriteCompanies[i] is the list of favorites companies for the ith person (indexed from 0).
Return the indices of people whose list of favorite companies is not a subset of any other list of favorites companies. You must return the indices in increasing order.
 
Example 1:
Input: favoriteCompanies = [["leetcode","google","facebook"],["google","microsoft"],["google","facebook"],["google"],["amazon"]]
Output: [0,1,4] 
Explanation: 
Person with index=2 has favoriteCompanies[2]=["google","facebook"] which is a subset of favoriteCompanies[0]=["leetcode","google","facebook"] corresponding to the person with index 0. 
Person with index=3 has favoriteCompanies[3]=["google"] which is a subset of favoriteCompanies[0]=["leetcode","google","facebook"] and favoriteCompanies[1]=["google","microsoft"]. 
Other lists of favorite companies are not a subset of another list, therefore, the answer is [0,1,4].

Example 2:
Input: favoriteCompanies = [["leetcode","google","facebook"],["leetcode","amazon"],["facebook","google"]]
Output: [0,1] 
Explanation: In this case favoriteCompanies[2]=["facebook","google"] is a subset of favoriteCompanies[0]=["leetcode","google","facebook"], therefore, the answer is [0,1].

Example 3:
Input: favoriteCompanies = [["leetcode"],["google"],["facebook"],["amazon"]]
Output: [0,1,2,3]

 
Constraints:

1 <= favoriteCompanies.length <= 100
1 <= favoriteCompanies[i].length <= 500
1 <= favoriteCompanies[i][j].length <= 20
All strings in favoriteCompanies[i] are distinct.
All lists of favorite companies are distinct, that is, If we sort alphabetically each list then favoriteCompanies[i] != favoriteCompanies[j].
All strings consist of lowercase English letters only.

Difficulty: interview

Starter code:

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        

Solutions:
class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        result = []
        fcSet = [set(fc) for fc in favoriteCompanies]
        n = len(favoriteCompanies)
        for i, fcs1 in enumerate(fcSet):
            for j, fcs2 in enumerate(fcSet):
                if i==j:
                    continue
                if fcs1<fcs2:
                    break
            else:
                result.append(i)
        return result

class Person:
    def __init__(self, index, favoriteCompanies):
        self.index = index
        self.favoriteCompanies = set(favoriteCompanies)
        self.size = len(favoriteCompanies)
    
    def __repr__(self):
        return \"{}\".format(self.favoriteCompanies)

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        people = [Person(i, l) for i, l in enumerate(favoriteCompanies)]
        people.sort(key = lambda person : person.size, reverse = True)
        
        res = []
        for i in range(len(people)):
            contained = False
            for j in range(i):
                if people[i].favoriteCompanies.issubset(people[j].favoriteCompanies):
                    contained = True
                    break
            if not contained:
                res.append(people[i].index)
        
        return sorted(res)

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        n = len(favoriteCompanies)
        res = list(range(n))
        array_of_sets = [set(company) for company in favoriteCompanies]
        for i in range(n):
            for j in range(n):
                if i != j:
                    if array_of_sets[i].issubset(array_of_sets[j]):
                        res.remove(i)
                        break
                        
        return res



class Solution:
  def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
    result = []
    for x in range(0, len(favoriteCompanies)):
      flag = True
      for y in range(0, len(favoriteCompanies)):
        if x == y:
          continue

        setx = set(favoriteCompanies[x])
        sety = set(favoriteCompanies[y])

        if setx.issubset(sety):

          flag = False
          break

      if flag:
        result.append(x)

    return sorted(result)

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        return [i for i, s1 in enumerate(favoriteCompanies) 
                if not any(set(s1).issubset(s2) for s2 in favoriteCompanies if s1 is not s2)]

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        A = favoriteCompanies
        location = {tuple(val):idx for idx, val in enumerate(A)}
        A.sort(key=lambda x: len(x))
        res = []
        for i in range(len(A)):
            for j in range(i+1, len(A)):
                if set(A[i]) & set(A[j]) == set(A[i]):
                    break
            else:
                res.append(location[tuple(A[i])])

        res.sort()    
        return res

class Solution:
    def peopleIndexes(self, f: List[List[str]]) -> List[int]:
        
        ans = []
        l = 0
        flag = False
        for lists in f:
            flag = False
            for lists2 in f:
                # print(lists)
                # print(lists2)
                if(lists == lists2):
                    continue
                if set(lists).issubset(set(lists2)):
                    # print(\"in\
\")
                    flag = True
                    break
            if flag == False:
                ans.append(l)
                    
            l = l+1   
            
        return ans
        

class Solution(object):
    def peopleIndexes(self, favoriteCompanies):
        \"\"\"
        :type favoriteCompanies: List[List[str]]
        :rtype: List[int]
        \"\"\"
        noSubset = []
        # print(len(favoriteCompanies))
        for i in range(len(favoriteCompanies)):
            people = favoriteCompanies.copy()
            people.pop(i)
            # print(i)
            # print(favoriteCompanies)
            index = favoriteCompanies[i]
            subsetStatus = [set(index).issubset(set(x)) for x in people]
            if any(subsetStatus) == True:
                # print(\"True\")
                continue
            else:
                # print('False')
                noSubset.append(i)
        return noSubset 

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:    
        
        order = {tuple(value):idx for idx, value in enumerate(favoriteCompanies)}
        favoriteCompanies  = sorted(favoriteCompanies,key=len,reverse=True)
        ans = []
        visited = []
        for fav in favoriteCompanies:
            
            find = 0
            for v in visited: 
                if set(v) & set(fav) == set(fav):
                    find = 1
                    break
            if find == 0:
                visited.append(fav)
                ans.append(order[tuple(fav)])
        
            
        return sorted(ans)

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        l=[0]*len(favoriteCompanies)
        p=[]
        for i in range(len(favoriteCompanies)):
            
            if l[i]==0:
                p.append(i)
                temp=set(favoriteCompanies[i])
                for j in range(i+1,len(favoriteCompanies)):
                    if temp & set(favoriteCompanies[j])==temp:
                        l[i]=1
                    
                        p[-1]=j
                        temp=set(favoriteCompanies[j])
                    elif temp & set(favoriteCompanies[j])==set(favoriteCompanies[j]):
                        l[j]=1
            
        p=set(p)            
        p=list(p)  
        p.sort()
        return  p              
                        
            


class Solution:
    def peopleIndexes(self, com: List[List[str]]) -> List[int]:
        c = com[:]
        com.sort(key=lambda x:-len(x))
        index = 1
        while index < len(com):
            curr = set(com[index])
            if any(set(com[i]) & curr == curr for i in range(index)):
                com.pop(index)
            else:
                index += 1
        res = []
        for i in com:
            for j in range(len(c)):
                if i == c[j]:
                    res.append(j)
        return sorted(res)

class Solution:
    def peopleIndexes(self, fav: List[List[str]]) -> List[int]:
        l=[]
        l1=[]
        for i in range(len(fav)):
            for j in range(len(fav)):
                
                if j is not i and set(fav[i]).issubset(set(fav[j])):
                    l.append(i)
        for i in range(len(fav)):
            if i not in l:
                l1.append(i)
        return l1

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        fev_set = []
        for i in favoriteCompanies:
            tmp = set()
            for j in i:
                tmp.add(j)
            fev_set.append(tmp)
        ans = []
        for ind, i in enumerate(fev_set):
            flag = 0
            for i2, j in enumerate(fev_set):
                if i2 != ind and i <= j:
                    flag = 1
                    break
            if not flag:
                ans.append(ind)
        return ans

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        def isSubset(lst1, lst2):
            if len(lst1) > len(lst2):
                return False
            largerSet = set()
            for elt in lst2:
                largerSet.add(elt)
            for elt in lst1:
                if elt not in largerSet:
                    return False
            return True
        return [i for i in range(len(favoriteCompanies)) if not any(j != i and isSubset(favoriteCompanies[i], favoriteCompanies[j]) for j in range(len(favoriteCompanies)))]
                


class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        res = []
        l = len(favoriteCompanies)
        for i in range(l):
            f = 0
            for j in range(l):
                if i != j:
                    if set(favoriteCompanies[i]).issubset(set(favoriteCompanies[j])):
                        f=1
                        break
            if f==0:
                res.append(i)
        return res

class Solution:
    def peopleIndexes(self, fc: List[List[str]]) -> List[int]:
        def helper(s, b):
            return len(set(s).intersection(set(b))) == len(s)
        
        n = len(fc)
        out = []
        for i in range(n):
            f = fc.pop(0)
            for rest in fc:
                if helper(f, rest):
                    out.append(i)
                    break
            fc.append(f)

        return sorted(list(set(range(n)).difference(set(out))))

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        def isSubset(lst1, lst2):
            largerSet = set()
            for elt in lst2:
                largerSet.add(elt)
            for elt in lst1:
                if elt not in largerSet:
                    return False
            return True
        return [i for i in range(len(favoriteCompanies)) if not any(j != i and isSubset(favoriteCompanies[i], favoriteCompanies[j]) for j in range(len(favoriteCompanies)))]
                


class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        no_overlap = []
        
        for i in range(len(favoriteCompanies)):
            flag = True
            for j in range(len(favoriteCompanies)):
                if i == j:
                    continue
                if len(set(favoriteCompanies[i]) - set(favoriteCompanies[j])) == 0:
                    flag = False
                    break
                
            if flag:
                no_overlap.append(i)
        
        return no_overlap

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        ret = []        
        # for ind, i in enumerate(favoriteCompanies):
        #     favoriteCompanies[ind] = set(sorted(i))
        for ind, current_person in enumerate(favoriteCompanies):
            check = False
            for j in range(len(favoriteCompanies)):
                if ind==j: continue
                previous_person = favoriteCompanies[j]
                if len(list(set(current_person) & set(previous_person)))==len(current_person):
                    check = True
                    break
            if not check:
                ret.append(ind)
        return ret


class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        #15
        mp = {}
        num_person = len(favoriteCompanies)
        for i in range(num_person):
            p = favoriteCompanies[i]
            for v in p:
                if v not in mp:
                    mp[v] = set()
                mp[v].add(i)
        result = []
        for i in range(num_person):
            p = favoriteCompanies[i]
            common = {}
            found = False
            for v in p:
                for k in mp[v]:
                    if k not in common:
                        common[k] = 0
                    common[k] += 1
                    if common[k] == len(p) and k != i:
                        found = True
                        break
                if found == True:
                    break
            if found == False:
                result.append(i)
        return result

class Solution:
    def peopleIndexes(self, A: List[List[str]]) -> List[int]:
        A = [set(A[i]) for i in range(len(A))]
        answer = []
        for i in range(len(A)):
            answer.append(i)
            for j in range(len(A)):
                if i != j and len(A[i]|A[j]) == len(A[j]):
                    answer.pop()
                    break
        return answer


class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        LEN = len(favoriteCompanies)
        ans = []
        for i in range(LEN):
            found = False
            for j in range(LEN):
                if i != j:
                    s1 = set(favoriteCompanies[i])
                    s2 = set(favoriteCompanies[j])
                    if len(s1 & s2) == len(s1):
                        found = True
                
            if not found:
                ans.append(i)
        return ans

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        subsets=set()
        res=[]
        for i in range(len(favoriteCompanies)):
            for j in range(len(favoriteCompanies)):
                if i!=j and set(favoriteCompanies[i]).issubset(favoriteCompanies[j]):
                    subsets.add(i)
        for i in range(len(favoriteCompanies)):
            if i not in subsets:
                res.append(i)
        return res

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        fev_set = []
        for i in favoriteCompanies:
            tmp = set()
            for j in i:
                tmp.add(j)
            fev_set.append(tmp)
        print(fev_set)
        ans = []
        for ind, i in enumerate(fev_set):
            flag = 0
            for i2, j in enumerate(fev_set):
                if i2 != ind and i <= j:
                    flag = 1
                    break
            if not flag:
                ans.append(ind)
        return ans

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        result = []
        for i in range(len(favoriteCompanies)):
            f = True
            for x in favoriteCompanies[:i] + favoriteCompanies[i+1:]:
                if set(favoriteCompanies[i]).intersection(set(x)) == set(favoriteCompanies[i]):
                    f = False
                    break
            if f:
                result.append(i)
        return result


class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        ans = []
        
        for i in range(len(favoriteCompanies)):
            for j in range(len(favoriteCompanies)):
                if i != j:
                    if len(set(favoriteCompanies[i]) & set(favoriteCompanies[j])) == len(set(favoriteCompanies[i])):
                        break
            else:
                ans.append(i)
        return ans


class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        ans=[]
        for i in range(len(favoriteCompanies)):
            flag=0
            for j in range(len(favoriteCompanies)):
            
                if (set(favoriteCompanies[i]) & set(favoriteCompanies[j])) == set(favoriteCompanies[i]) and i!=j:
                    flag=1
                    break
            if flag==0:
                ans.append(i)
                
        return ans
                    
                
        
        


class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        dic = collections.defaultdict(list)
        fc = favoriteCompanies
        for i, p in enumerate(fc):
            for c in p:
                dic[c].append(i)
        n = len(fc)
        counter = [[0] * n for _ in range(n)]
        for l in dic.values():
            for i in range(len(l)):
                for j in range(i + 1, len(l)):
                    counter[l[i]][l[j]] += 1
                    counter[l[j]][l[i]] += 1
        ans = set()
        for i in range(n):
            for j in range(n):
                if counter[i][j] == len(fc[i]):
                    ans.add(i)
                    break
               
        return sorted(set(range(n)) - ans)

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        dic = {}
        ind = 0
        profile = []
        for companies in favoriteCompanies:
            for company in companies:
                if company not in dic:
                    dic[company] = ind
                    ind += 1
        
        for companies in favoriteCompanies:
            val = 0
            for company in companies:
                val += 2**dic[company]
            profile.append(val)
        
        res = []
        for i in range(len(profile)):
            flag = True
            for j in range(len(profile)):
                if i == j:
                    continue
                elif profile[i] | profile[j] == profile[j]:
                    flag = False
                    break
            if flag:
                res.append(i)
        return res


class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        dic_companies = {}
        inx = 0
        for companies in favoriteCompanies:
            for company in companies:
                if company not in dic_companies:
                    dic_companies[company] = inx
                    inx += 1

        favorite_comp = []
        for companies in favoriteCompanies:
            val = 0
            for company in companies:
                val += 2** dic_companies[company]
            favorite_comp.append(val)

        res = []

        for i in range(len(favorite_comp)):
            flag = True
            for j in range(len(favorite_comp)):
                if i == j:continue
                if favorite_comp[i] | favorite_comp[j] == favorite_comp[j]:
                    flag = False
                    break
            if flag:
                res.append(i)

        return res

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        ans = []
        
        for i in range(len(favoriteCompanies)):
            for j in range(len(favoriteCompanies)):
                if i != j:
                    if len(set(favoriteCompanies[i]) & set(favoriteCompanies[j])) == len(set(favoriteCompanies[i])):
                        break
            else:
                ans.append(i)
        return ans
        


class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        for u in favoriteCompanies:
            u.sort()
        L=len(favoriteCompanies)
        dic={}
        def check(i,j):
            if (i,j) in dic:
                return dic[(i,j)]
            else:
                stack1=favoriteCompanies[i].copy()
                stack2=favoriteCompanies[j].copy()
                while stack1 and stack2:
                    if stack2[0]!=stack1[0]:
                        stack2.pop(0)
                    elif stack2[0]==stack1[0]:
                        stack1.pop(0)
                        stack2.pop(0)
                if not stack1:
                    dic[(i,j)]=True
                    return True
                else:
                    dic[(i,j)]=False
                    return False
        ans=[]
        for i in range(L):
            status=0
            for j in range(L):
                if j!=i and check(i,j):
                    status=1
                    break
            if status==0:
                ans.append(i)
        return ans

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        for u in favoriteCompanies:
            u.sort()
        L=len(favoriteCompanies)
        dic={}
        def check(i,j):
            if (i,j) in dic:
                return dic[(i,j)]
            else:
                status=0
                stack1=favoriteCompanies[i].copy()
                stack2=favoriteCompanies[j].copy()
                while stack1 and stack2:
                    if stack2[0]!=stack1[0]:
                        status=1
                        stack2.pop(0)
                    elif stack2[0]==stack1[0]:
                        stack1.pop(0)
                        stack2.pop(0)
                if not stack1:
                    dic[(i,j)]=True
                    if status==1:
                        dic[(j,i)]=False
                    return True
                else:
                    dic[(i,j)]=False
                    return False
        ans=[]
        for i in range(L):
            status=0
            for j in range(L):
                if j!=i and check(i,j):
                    status=1
                    break
            if status==0:
                ans.append(i)
        return ans

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        n = len(favoriteCompanies)
        
        for i in range(n):
            favoriteCompanies[i] = set(favoriteCompanies[i])
        
        ans = []
        
        for i in range(n):
            for j in range(n):
                if i!=j and favoriteCompanies[i]<=favoriteCompanies[j]:
                    break
            else:
                ans.append(i)
        
        return ans

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        frequency_dict = dict()
        word_tracker = dict()
        
        for index, companies in enumerate(favoriteCompanies):
            for company in companies:
                if company not in word_tracker:
                    word_tracker[company] = []
                
                for matched_index in word_tracker[company]:
                    if matched_index not in list(frequency_dict.keys()):
                        frequency_dict[matched_index] = dict()
                    if index not in list(frequency_dict[matched_index].keys()):
                        frequency_dict[matched_index][index] = 0

                    if index not in list(frequency_dict.keys()):
                        frequency_dict[index] = dict()
                    if matched_index not in list(frequency_dict[index].keys()):
                        frequency_dict[index][matched_index] = 0
                        
                    frequency_dict[matched_index][index] += 1
                    frequency_dict[index][matched_index] += 1
                    
                word_tracker[company].append(index)
        
        ret_list = []
        for index, companies in enumerate(favoriteCompanies):
            is_subset = False
            if index in list(frequency_dict.keys()):
                for key in list(frequency_dict[index].keys()):
                    if frequency_dict[index][key] >= len(companies):
                        is_subset = True
                        break
            
            if not(is_subset):
                ret_list.append(index)
        return ret_list
        


class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        c_id = 0
        h = {}
        for fc in favoriteCompanies:
            for c in fc:
                if c in h:
                    continue
                h[c] = c_id
                c_id += 1
        for idx, fc in enumerate(favoriteCompanies):
            fc.sort(key=lambda x: h[x])
            
        N = len(favoriteCompanies)
        ret = []
        for i in range(N):
            for j in range(N):
                if i == j:
                    continue
                ci, cj = favoriteCompanies[i], favoriteCompanies[j]
                iidx, jidx = 0, 0
                while iidx < len(ci) and jidx < len(cj):
                    iidx += ci[iidx] == cj[jidx]
                    jidx += 1
                if iidx == len(ci):
                    break
            else:
                ret.append(i)
        return ret 


class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        res = []
        l = len(favoriteCompanies)
        for i in range(l):
            f = 0
            for j in range(l):
                if i != j:
                    if (set(favoriteCompanies[i]) | set(favoriteCompanies[j])) == set(favoriteCompanies[j]):
                        f=1
                        break
            if f==0:
                res.append(i)
        return res

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        a = [set(y) for y in favoriteCompanies]
        def check(i):
            return all([i == j or not a[i].issubset(a[j]) for j in range(len(a))])
        return [i for i in range(len(a)) if check(i)]

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        sets = [set(x) for x in favoriteCompanies]
        
        for i, companies in enumerate(sets):
            for j, other in enumerate(sets):
                if i == j: continue
                if companies <= other:
                    break
            else:
                yield i

class Solution:
    def peopleIndexes(self, favorite_companies: List[List[str]]) -> List[int]:
        company_set_per_person = []
        for i, company_list in enumerate(favorite_companies):
            company_set = set(company_list)
            found = False
            for j, (other_company_set, k) in enumerate(company_set_per_person):
                if company_set >= other_company_set:
                    company_set_per_person[j] = (company_set, i)
                    found = True
                    break
                if company_set <= other_company_set:
                    found = True
                    break
            if not found:
                company_set_per_person.append((company_set, i))
        
        # print(company_set_per_person)
        
        ans = []
        for i, company_list in enumerate(favorite_companies):
            company_set = set(company_list)
            found = False
            for other_company_set, j in company_set_per_person:
                if company_set <= other_company_set and i != j:
                    found = True
                    break
            if not found:
                ans.append(i)
        return ans

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        
        d={}
        n=len(favoriteCompanies)
        A=[]
        for j,arr in enumerate(favoriteCompanies):
            A.append((arr,j))
        
        A.sort(key=lambda x:len(x[0]),reverse=True)
        print(A)
        ans=[]
        s1=set()
        for i in range(n):
            k=A[i][1]
            s1.add(k)
            temp=s1
            for j,c in  enumerate(A[i][0]):
                if c not in d:
                    d[c]=set([k])
                else:
                    d[c].add(k)
                temp=temp.intersection(d[c])
                
                    
            if len(temp)==1:
                ans.append(k)
            
                    
            
                
        ans.sort()
                
        
        return ans
                
                        
                    
                    
                    
            
        
        


class Solution(object):
    \"\"\"
    使用类似并查集的解法

    # 思路

    有包含关系的为一组，输入每个群组的头索引

    # 注意

    不能直接用并查集，比如 0, 3 连通了, 使用并查集处理到 1, 3 时会将其连通为 0, 1, 3

    \"\"\"

    def peopleIndexes(self, favoriteCompanies):
        \"\"\"
        :type favoriteCompanies: List[List[str]]
        :rtype: List[int]
        \"\"\"

        n_person = len(favoriteCompanies)

        companies = [set(companies) for companies in favoriteCompanies]

        parent = [i for i in range(n_person)]

        for person_a in range(n_person):
            for person_b in range(person_a + 1, n_person):  # 对所有的人两两处理
                if companies[person_a].issubset(companies[person_b]):
                    parent[person_a] = parent[person_b]
                elif companies[person_b].issubset(companies[person_a]):
                    parent[person_b] = parent[person_a]

        roots = set()
        for person in range(n_person):
            root = parent[person]
            while root != parent[root]:
                root = parent[root]
            roots.add(root)
        return sorted(list(roots))




class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        
        
        htable = {}
        for i, j in enumerate(favoriteCompanies):
            htable[i] = set(j)
        result = []    
        for k in htable:
            flag = True
            for j in list(htable.values()):
                if htable[k] == j:
                    continue
                elif htable[k].issubset(j):
                    flag = False
                    break

            if flag:
                result.append(k)
        print(result)
        return result
                    


class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        # ans = []
        # s = [set(cs) for cs in favoriteCompanies]
        # print(s)
        # for i, s1 in enumerate(s):
        #     if all (i == j or not s1.issubset(s2) for j, s2 in enumerate(s)):
        #         ans.append(i)
        # return ans
    
        people = []
        sets = [set(Co) for Co in favoriteCompanies]
        for i, a in enumerate(sets):
            for j, b in enumerate(sets):
                if i == j: continue
                if a.issubset(b): break
            else:
                people.append(i)

        return people

class Solution:
    def _subset(self, fav, result):
        for x in result:
            if not fav - x:
                return True
        return False

    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        favorite_companies = [tuple(sorted(x)) for x in favoriteCompanies]
        val_to_key = {x: i for i, x in enumerate(favorite_companies)}
        len_to_comp = collections.defaultdict(list)
        for x in favorite_companies:
            len_to_comp[len(x)].append(set(x))
        sorted_keys = sorted(len_to_comp, reverse=True)
        result = []
        for key in sorted_keys:
            curr = []
            for fav in len_to_comp[key]:
                if not self._subset(fav, result):
                    curr.append(fav)
            result += curr
        result = [tuple(sorted(x)) for x in result]
        return sorted([val_to_key[x] for x in result])


class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        
        cs = {w for f in favoriteCompanies for w in f}
        cs = {v: i for i, v in enumerate(cs)}
        fs = []
        for f in favoriteCompanies:
            i = 0
            for c in f:
                i |= 1 << cs[c]
            fs.append(i)
            
        ans = []
        for i in range(len(fs)):
            f = 1
            for j in range(len(fs)):
                if i == j: continue
                if fs[i] | fs[j] == fs[j]:
                    f ^= 1
                    break
            if f:
                ans.append(i)
        return ans


class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        res = []
        subsets = sorted([[set(companies), i]
                            for i, companies in enumerate(favoriteCompanies)], key=lambda x: len(x[0]))
        for i, companies in enumerate(subsets):
            companies, res_i = companies
            for j, companies2 in enumerate(subsets[i+1:], i+1):
                companies2 = companies2[0]
                if all(company in companies2 for company in companies):
                    break
            else:
                res += res_i,
        return sorted(res)

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        favorite_index = collections.defaultdict(set)
        for fav in range(len(favoriteCompanies)):
            for company in favoriteCompanies[fav]:
                favorite_index[company].add(fav)
        
        result = []
        for fav in range(len(favoriteCompanies)):
            subsets = set()
            first = True
            for company in favoriteCompanies[fav]:
                if first:
                    subsets = subsets.union(favorite_index[company])
                    first = False
                else:
                    subsets = subsets.intersection(favorite_index[company])
                    # print(f'for {fav} on {company}: {subsets}')
                if len(subsets) == 1:
                    result.append(fav)
                    break
        return result

def comp(a,b):
    for i in a:
        if(i not in b):
            return 0
    return 1
class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        favoriteCompanies = [(j,i) for i,j in enumerate(favoriteCompanies)]
        x = sorted(favoriteCompanies, key = lambda x:len(x[0]), reverse = True)
        y = [i[1] for i in x]
        x = [i[0] for i in x]
        arrd = []
        for i in range(len(x)):
            d = {}
            for j in range(len(x[i])):
                d[x[i][j]] = 1
            arrd.append(d)
        # print(arrd)
        ind = [0]*len(x)
        for j in range(len(x)):
            for i in range(j-1,-1,-1):
                if(comp(arrd[j], arrd[i])):
                    ind[j] = 1
                    break
        f = []
        for i in range(len(ind)):
            if(ind[i] == 0):
                f.append(y[i])
        return sorted(f)


class Solution:
    def peopleIndexes(self, A: List[List[str]]) -> List[int]:
        d = {i: set(v) for i, v in enumerate(A)}
        res = []
        for i in range(len(A)):
            isSubset = False
            for j in range(len(A)):
                if i == j:
                    continue
                if d[i].issubset(d[j]):
                    isSubset = True
                    break
            if not isSubset: res.append(i)         
        return res    

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        g = collections.defaultdict(set)
        self.parent = [i for i in range(len(favoriteCompanies))]
        for i, companies in enumerate(favoriteCompanies):
            g[i] = set(companies)
        for i in range(len(favoriteCompanies)):
            for j in range(i+1,len(favoriteCompanies)):
                a,b = self.find(i),self.find(j)
                if a != b:
                    if g[a] >= g[b]:
                        self.parent[b] = a
                    elif g[b] > g[a]:
                        self.parent[a] = b
        res = set()
        for i in range(len(favoriteCompanies)):
            res.add(self.find(i))
        return sorted(res)
        
    def find(self,i):
        while self.parent[i] != i:
            self.parent[i] = self.parent[self.parent[i]]
            i = self.parent[i]
        return i


class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        d={}
        for ind,company in enumerate(favoriteCompanies):
            for e in company:
                if e not in d:
                    d[e]=set()
                d[e].add(ind)
        #print('d',d)
        output=[]
        for ind,company in enumerate(favoriteCompanies):
            temp=d[company[0]]
            for e in company[1:]:
                temp=temp.intersection(d[e])
            if len(temp)<=1:
                output.append(ind)
        return output
            


class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        ans = []
        s = [set(c) for c in favoriteCompanies]
        for i, s1 in enumerate(s):
            if all(i==j or not s1.issubset(s2) for j, s2 in enumerate(s)):
                ans.append(i)
        return ans

class Solution:
    def peopleIndexes(self, fv: List[List[str]]) -> List[int]:
        
        dic = defaultdict(lambda : set())
        for i in range(len(fv)):
            for cmp in fv[i]:
                dic[cmp].add(i)
        ans = []
        ind = 0
        for lst in fv:
            st = None
            for cmp in lst:
                if st:
                    st &= dic[cmp]
                else:
                    st = dic[cmp].copy()
            if len(st) == 1:
                ans.append(ind)
            ind += 1
        return sorted(ans)


class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        # ans = []
        # s = [set(cs) for cs in favoriteCompanies]
        # print(s)
        # for i, s1 in enumerate(s):
        #     if all (i == j or not s1.issubset(s2) for j, s2 in enumerate(s)):
        #         ans.append(i)
        # return ans
    
        people = []
        sets = [set(a) for a in favoriteCompanies]
        for i, a in enumerate(sets):
            for j, b in enumerate(sets):
                if i == j: continue
                if a.issubset(b): break
            else:
                people.append(i)

        return people

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        graph = collections.defaultdict(set)
        for i, companies in enumerate(favoriteCompanies): 
            for comp in companies: 
                graph[comp].add(i)
        ans = []
        for i, companies in enumerate(favoriteCompanies): 
            groups = None
            for comp in companies: 
                if groups is None: 
                    groups = set(x for x in graph[comp])
                else: 
                    groups &= graph[comp]
            if len(groups) == 1: 
                ans.append(i)
        return ans
                
        

        # build trie
#         trie = {}
#         for companies in favoriteCompanies: 
#             companies.sort()
#             for c in (companies[i:] for i in range(len(companies))):
#                 node = trie
#                 for e in c: 
#                     if e not in node: 
#                         node[e] = {'#': 0}
#                     node = node[e]
#                     node['#'] += 1
#         ans = []
#         for i, companies in enumerate(favoriteCompanies): 
#             node = trie
#             for c in companies: 
#                 node = node[c]
#             if node['#'] == 1: ans.append(i)
#         return ans
    
        
            
            
                    
            
            


class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        graph = collections.defaultdict(set)
        for i, companies in enumerate(favoriteCompanies): 
            for comp in companies: 
                graph[comp].add(i)
        ans = []
        for i, companies in enumerate(favoriteCompanies): 
            groups = None
            for comp in companies: 
                if groups is None: 
                    groups = set(x for x in graph[comp])
                else: 
                    groups &= graph[comp]
            if len(groups) == 1: ans.append(i)
        return ans
                
        

        # build trie
#         trie = {}
#         for companies in favoriteCompanies: 
#             companies.sort()
#             for c in (companies[i:] for i in range(len(companies))):
#                 node = trie
#                 for e in c: 
#                     if e not in node: 
#                         node[e] = {'#': 0}
#                     node = node[e]
#                     node['#'] += 1
#         ans = []
#         for i, companies in enumerate(favoriteCompanies): 
#             node = trie
#             for c in companies: 
#                 node = node[c]
#             if node['#'] == 1: ans.append(i)
#         return ans
    
        
            
            
                    
            
            


class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        companies = favoriteCompanies[:]
        for i in range(len(companies)):
            companies[i] = set(companies[i])       
        
        subsets = []
        for i in range(len(companies)):
            currSet = companies[i]
            for j in range(len(companies)):
                if i != j:
                    count = 0
                    for each in currSet:
                        if each in companies[j]:
                            count += 1
                        else:
                            break
                    if count == len(currSet):
                        subsets.append(i)
                        break
        
        size = len(favoriteCompanies) - len(subsets)
        res = [None] * size
        curr = 0
        subsets = set(subsets)
        for i in range(len(favoriteCompanies)):
            if i not in subsets:
                res[curr] = i
                curr += 1
                
        return res

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        dict = defaultdict(int)
        for i,lst in enumerate(favoriteCompanies):
            people_mask = 1<<i
            for comp in lst:
                dict[comp] += people_mask
                
        res = []
        for i,lst in enumerate(favoriteCompanies):
            other_people = ~(1<<i)
            for comp in lst:
                other_people &= dict[comp]
                if not other_people:
                    break
            if not other_people:
                res.append(i)
        return res


class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        
        
        name2idx = {}
        group = {}
        
        for i in range(len(favoriteCompanies)):    
            for item in favoriteCompanies[i]:
                if not item in name2idx:
                    name2idx[item] = len(name2idx)
        
        for i in range(len(favoriteCompanies)):
            favoriteCompanies[i] = [name2idx[x] for x in favoriteCompanies[i]]
        
        for i in range(len(favoriteCompanies)):
            group[tuple([x for x in favoriteCompanies[i]])] = i
        
        favoriteCompanies = sorted(favoriteCompanies, key=lambda x: len(x), reverse=True)
        
        # print(group)
        # print(favoriteCompanies)
        ans = []
        for i in range(len(favoriteCompanies)):
            if len(ans)==0:
                ans.append(group[tuple([x for x in favoriteCompanies[i]])])
                continue
            
            cur_set = set(favoriteCompanies[i])
            flag = True
            for j in range(i):
                pre_set = set(favoriteCompanies[j])
                
                if cur_set.issubset(pre_set):
                    flag = False
                    break
            
            if flag:
                ans.append(group[tuple([x for x in favoriteCompanies[i]])])
        
        ans.sort()
        return ans
                    
                


class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        res = []
        subsets = [[set(companies), i]
                            for i, companies in enumerate(favoriteCompanies)]
        for i, companies in enumerate(subsets):
            companies, res_i = companies
            for j, companies2 in enumerate(subsets):
                if i == j:
                    continue
                companies2 = companies2[0]
                if all(company in companies2 for company in companies):
                    break
            else:
                res += res_i,
        return sorted(res)

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        ans = []
        s = [set(comp) for comp in favoriteCompanies]
        # turn the companies into sets
        # check that all point have i == j or s1 is not a subset s2
        for i , s1 in enumerate(s):
            if all(i==j or not s1.issubset(s2) for j, s2 in enumerate(s)):
                ans.append(i)
        return ans
            
        


class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:

        D = collections.defaultdict(int)
        
        for i, cs in enumerate(favoriteCompanies):
            p = 1 << i
            
            for c in cs:
                D[c] |= p
                
        res = []
        ac = 2 ** len(favoriteCompanies) - 1
        
        for i, cs in enumerate(favoriteCompanies):
            p = 1 << i
            pc = ac
            
            for c in cs:
                pc &= D[c]
            
            if p == pc:
                res.append(i)
        
        return res

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        coms = sorted([[set(cs), oi] for oi, cs in enumerate(favoriteCompanies)], key=lambda x: len(x[0]))
        ret = []
        for i, com in enumerate(coms):
            com1, oi = com
            is_sub = False
            for com2, _ in coms[i+1:]:
                if not com1 - com2:
                    is_sub = True
                    break
            if not is_sub:
                ret.append(oi)
        return sorted(ret)

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        if len(favoriteCompanies) == 0:
            return []
        answer = []
        listOfSets = [ [set(favoriteCompanies[index]), index] for index in range(len(favoriteCompanies)) ]
        listOfSets.sort(key=lambda pair : len(pair[0]))
        print(listOfSets)
        for i in range(len(listOfSets)):
            subset = False
            for j in range(i+1, len(listOfSets)):
                #print(f\"current {listOfSets[i][0]} subset of {listOfSets[j][0]}\")
                if listOfSets[i][0].issubset(listOfSets[j][0]):
                    subset = True
                    #print(\"Found subset\")
                    break
            if subset == False:
                answer.append(listOfSets[i][1])
        answer.sort()
        return answer

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        idx = {}
        encoded = []
        n = len(favoriteCompanies)
        for l in favoriteCompanies:
            b = 0
            for c in l:
                idx.setdefault(c, len(idx))
                b |= 1 << idx[c]
            encoded.append(b)
        ans = []
        for i, b1 in enumerate(encoded):
            for b2 in encoded:
                if b1 | b2 == b2 and b1 != b2:
                    break
            else:
                ans.append(i)
        return ans
        


class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        lst = []
        n = len(favoriteCompanies)
        for i in range(n):
            c = set(favoriteCompanies[i])
            lst.append([c, i])
        lst.sort(key = lambda x: -len(x[0]))
        subset = set()
        for i in range (n - 1, 0, -1):
            for j in range(i-1, -1, -1):
                if lst[j][0] & lst[i][0] == lst[i][0]:
                    subset.add(lst[i][1])
        return [i for i in range(n) if i not in subset]

class Solution:
    def peopleIndexes(self, favorites: List[List[str]]) -> List[int]:
        # res = []
        # l = len(favoriteCompanies)
        # for i in range(l):
        #     f = 0
        #     for j in range(l):
        #         if i != j:
        #             if set(favoriteCompanies[i]).issubset(set(favoriteCompanies[j])):
        #                 f=1
        #                 break
        #     if f==0:
        #         res.append(i)
        # return res
        
        parents = []
        parent_sets = []
        for i in sorted(range(len(favorites)), key=lambda i: len(favorites[i]), reverse=True):
            c = set(favorites[i])
            
            is_parent = True
            for p in parent_sets:
                if c.issubset(p):
                    is_parent = False
                    break
            
            if is_parent:
                parents.append(i)
                parent_sets.append(c)
            
        return sorted(parents)

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        n = len(favoriteCompanies)
        res = list(range(n))
        seen = set()
        array_of_sets = [set(company) for company in favoriteCompanies]
        for i in range(n-1):
            for j in range(i+1, n):
                if i != j:
                    remind = array_of_sets[i] & array_of_sets[j]
                    if remind == array_of_sets[i]:
                        if i not in seen:
                            seen.add(i)
                            res.remove(i)
                    if remind == array_of_sets[j]:
                        if j not in seen:
                            seen.add(j)
                            res.remove(j)
        return res


class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        companies_set = [set(c) for c in favoriteCompanies]
        
        res = []
        for i, s1 in enumerate(companies_set):
            is_subset = False
            for j, s2 in enumerate(companies_set):
                if i == j:
                    continue
                if s1.issubset(s2):
                    is_subset = True
                
            if not is_subset:
                res.append(i)
            
        return res

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        length = len(favoriteCompanies)
        for i in range(length):
            favoriteCompanies[i] = set(favoriteCompanies[i])
        res = []
        for i in range(length):
            pattern = favoriteCompanies[i]
            for flist in favoriteCompanies:
                if pattern < flist: break
            else:
                res.append(i)
        return res

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        ans = []
        s = [set(c) for c in favoriteCompanies]
        for i, s1 in enumerate(s):
            if all( i == j or not(s1.issubset(s2)) for j, s2 in enumerate(s)):
                ans.append(i)
                    
        return ans

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        res = []
        sets = [set(a) for a in favoriteCompanies]
        for i, a in enumerate(sets):
            for j, b in enumerate(sets):
                if i == j: continue
                if a.issubset(b): break
            else:
                res.append(i)
        return res


class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        # s=set()
        # b=set()
        # x=s.intersection(b)
        glb=set()
        ct=0
        # d={}
        ds={}
        for i in favoriteCompanies:
            for j in i:
                if j not in glb:
                    ct=ct+1
                    ds[j]=ct
                    glb.add(j)
        d=collections.defaultdict(set)
        
        for i in range(len(favoriteCompanies)):
            new=set()
            for j in favoriteCompanies[i]:
                new.add(ds[j])
                
            d[i]=new
        ar=[]
        for i in range(len(favoriteCompanies)):
            found=0
            for j in range(len(favoriteCompanies)):
                if i!=j:
                    x=d[i].intersection(d[j])
                    if x==d[i]:
                        found=1
                        break
            if found==0:
                ar.append(i)
                
        
        return ar

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        favoriteCompanies = [[len(favoriteCompanies[i]),i,set(favoriteCompanies[i])] for i in range(len(favoriteCompanies))]
        favoriteCompanies.sort()
        #print(favoriteCompanies)
        res = []
        for i in range(len(favoriteCompanies)):
            attendre = favoriteCompanies[i][2]
            flag = True
            for j in range(i+1,len(favoriteCompanies)):
                if not attendre - favoriteCompanies[j][2]:
                    flag = False
                    break
            if flag:
                res.append(favoriteCompanies[i][1])
        return sorted(res)      

from collections import defaultdict
class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        out = []
        d = defaultdict(list)
        for i,companies in enumerate(favoriteCompanies):
            for company in companies:
                d[company].append(i)
        for i,companies in enumerate(favoriteCompanies):
            s = set(d[companies[0]])
            for company in companies:
                s = s.intersection(d[company])
            if len(s) == 1:
                out.append(i)
        return out
        


class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        def judge(i):
            for j in range(n):
                if i != j:
                    contain = True
                    for x in favoriteCompanies[i]:
                        if x not in favoriteCompanies[j]:
                            contain = False
                            break
                    if contain:
                        return False
            return True
        
        n = len(favoriteCompanies)
        favoriteCompanies = list(map(set,favoriteCompanies))
        res = []
        for i in range(n):
            if judge(i): res.append(i)
        return res
                            


class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        
        favoriteCompanies = [set(i) for i in favoriteCompanies]
        visited = [False]*len(favoriteCompanies)
        res = [] 
        
        for i in range(len(favoriteCompanies)-1):
            if visited[i]:
                continue
            else:
                for j in range(i+1,len(favoriteCompanies)):
                    if favoriteCompanies[i].intersection(favoriteCompanies[j]) == favoriteCompanies[i]:
                        visited[i] = True
                        break
                    elif favoriteCompanies[i].intersection(favoriteCompanies[j]) == favoriteCompanies[j]:
                        visited[j] = True
                        
        for i in range(len(favoriteCompanies)):
            if not(visited[i]):
                res.append(i)
        return res
                
                        


class Solution:
    def peopleIndexes(self, company: List[List[str]]) -> List[int]:
        
        
        
        company = [set(i) for i in company]
        
        
        visited = [False]*len(company)
        
        for i in range(len(company)-1):
            if(visited[i]):
                continue
                
            root = company[i]
            for j in range(i+1,len(company)):
                child = company[j]
                if(len(root.intersection(child)) == len(root)):
                    visited[i] = True
                    break
                    
                elif(len(root.intersection(child)) == len(child)):
                    visited[j] = True
                    
        
        res = []
        
        for i in range(len(visited)):
            if(visited[i] == False):
                res.append(i)
                
        return res


class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        company = favoriteCompanies
        company = [set(i) for i in company]
        
        
        visited = [False]*len(company)
        
        for i in range(len(company)-1):
            if(visited[i]):
                continue
                
            root = company[i]
            for j in range(i+1,len(company)):
                child = company[j]
                if(len(root.intersection(child)) == len(root)):
                    visited[i] = True
                    break
                    
                elif(len(root.intersection(child)) == len(child)):
                    visited[j] = True
                    
        
        res = []
        
        for i in range(len(visited)):
            if(visited[i] == False):
                res.append(i)
                
        return res

class UnionFind:
    
    def __init__(self, favorites):
        self.n = len(favorites)
        self.arr = list(range(self.n))
        self.favorites = [set(x) for x in favorites]
        
    def union(self, a, b):
        \"\"\"Returns true if you can end search early, else False.\"\"\"
        a, b = self.find(a), self.find(b)
        if a == b:
            return True
        
        a_fav, b_fav = self.favorites[a], self.favorites[b]
        if a_fav.issubset(b_fav):
            self.arr[a] = b
            return True
        if b_fav.issubset(a_fav):
            self.arr[b] = a
            return True
        
        return False
        
    def find(self, a):
        head = a
        while self.arr[head] != head:
            head = self.arr[head]
            
        # path compression
        ptr = a
        while a != head:
            a = self.arr[a]
            self.arr[ptr] = head
            ptr = a
        
        return head
        
    def num_groups(self):
        return [i for i in range(self.n) if self.arr[i] == i]

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        \"\"\"
        API
        count_num_groups (head of each group will be people without subsets)
        union (if in same group, do nothing. If a is subset of b, a points to b.)
        \"\"\"
        uf = UnionFind(favoriteCompanies)
        n = len(favoriteCompanies)
        for i in range(n):
            for j in range(i + 1, n):
                if uf.union(i, j):
                    break
        return uf.num_groups()
        

class Solution:
    def peopleIndexes(self, company: List[List[str]]) -> List[int]:
        company = [set(i) for i in company]
        
        
        visited = [False]*len(company)
        
        for i in range(len(company)-1):
            if(visited[i]):
                continue
                
            root = company[i]
            for j in range(i+1,len(company)):
                child = company[j]
                if(len(root.intersection(child)) == len(root)):
                    visited[i] = True
                    break
                    
                elif(len(root.intersection(child)) == len(child)):
                    visited[j] = True
                    
        
        res = []
        
        for i in range(len(visited)):
            if(visited[i] == False):
                res.append(i)
                
        return res

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        c = set(); d = {} ; i = 0; com = []
        for j in favoriteCompanies:
            cur = set()
            for x in j:
                if x not in d: d[x] = i; i+=1
                cur.add(d[x])
            com += [cur]
        ans = []
        for i in range(len(com)):
            flag = False
            for j in range(len(com)):
                if i!=j:
                    if com[i].issubset(com[j]):
                        flag = True; break
            if not flag: ans += [i]
        return ans 

        


class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        company = favoriteCompanies
        company = [set(i) for i in company]
        print(company)
        
        visited = [False]*len(company)
        res = []        
        for i in range(len(company)-1):
            if(visited[i]):
                continue                
            root = company[i]
            for j in range(i+1,len(company)):
                child = company[j]
                if(len(root.intersection(child)) == len(root)):
                    visited[i] = True
                    break
                    
                elif(len(root.intersection(child)) == len(child)):
                    visited[j] = True
                    
        for i in range(len(company)):
            if not visited[i]:
                res.append(i)
                
        return res

class Solution:
    def peopleIndexes(self, A: List[List[str]]) -> List[int]:
        '''
        # 比赛用代码
        res = []
        A = [(v, i) for i, v in enumerate(A)]
        A.sort(key = lambda x: len(x[0]))
        A = A[::-1]
        visit = []
        for v, i in A:
            v = set(v)
            if visit:
                for t in visit:
                    if v.issubset(t):
                        break
                else:
                    res.append(i)
            else:
                res.append(i)
            visit.append(v)
        return sorted(res)
        '''
        # 暴力解法。set的&操作
        res = []
        fc = [set(f) for f in A]
        n = len(fc)
        for i in range(n):
            for j in range(n):
                if i != j and fc[i] & fc[j] == fc[i]:
                    break
            else:
                res.append(i)
        return res

class Solution:
    def peopleIndexes(self, A: List[List[str]]) -> List[int]:
        d = {i: set(v) for i, v in enumerate(A)}
        res = []
        for i in range(len(A)):
            subSet = True
            for j in range(len(A)):
                if i == j:
                    continue
                if len(d[i]) > len(d[j]):
                    continue
                if not d[i] - d[j]:
                    subSet = False
                    break
            if subSet: res.append(i)         
        return res

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        comp_dict={i:set(v) for i,v in enumerate(favoriteCompanies)}
        res=[]
        for i in range(len(favoriteCompanies)):
            subset=True
            for j in range(len(favoriteCompanies)):
                if i==j:
                    continue
                if not comp_dict[i]-comp_dict[j]:
                    subset=False
                    break
            if  subset:
                res.append(i)
        return res        
        
                    


class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        # favoriteCompanies=sorted(favoriteCompanies,key=lambda x:len(x))
        
        ls=[]
        for i in favoriteCompanies:
            ls.append(set(i))
        
        # print(ls)
        ans=[]
        for i in range(len(ls)):
            flag=0
            for j in range(len(ls)):
                if(i!=j):
                    tem=ls[i].intersection(ls[j])
                    if(tem==ls[i]):
                        flag=1
                        break

                
            if(flag==0):
                ans.append(i)
                
        return ans

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        f_C = []
        for company in favoriteCompanies:
            f_C.append(set(company))
        print(f_C)
        n = len(f_C)
        ans = []
        for i in range(n):
            flag = 1
            for j in range(n):
                if i==j:
                    continue
                if f_C[i]&f_C[j] == f_C[i]:
                    flag=0
                    break
            if flag==1:
                ans.append(i)
        return ans;

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        ans = []
        n = len(favoriteCompanies)
        f = [set(c) for c in favoriteCompanies ]
        for i in range(n):
            for j in range(n):
                if i != j and f[i] & f[j] == f[i]:
                    break
            else:
                ans.append(i)
        return ans


class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        # favoriteCompanies=sorted(favoriteCompanies,key=lambda x:len(x))
        
        ls=[]
        for i in favoriteCompanies:
            ls.append(set(i))
        
        print(ls)
        ans=[]
        for i in range(len(ls)):
            flag=0
            for j in range(len(ls)):
                if(i!=j):
                    tem=ls[i].intersection(ls[j])
                    if(tem==ls[i]):
                        flag=1
                        break

                
            if(flag==0):
                ans.append(i)
                
        return ans

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        from collections import Counter
        words = {}
        subsets = []
        for i, x in enumerate(favoriteCompanies):
            for y in x:
                if y not in words:
                    words[y] = [i]
                else:
                    words[y].append(i)
      

        for i, x in enumerate(favoriteCompanies):
            c = Counter()
            for y in x:
                c.update(words[y])
            for item in c.most_common():
                if item[0] != i:
                    if item[1] >= len(x):
                        break
                    else:
                        subsets.append(i)
                        break
                elif len(c) == 1:
                    subsets.append(i)
                    
        return subsets

\"\"\"

\"\"\"
class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        sets = [set(companies) for companies in favoriteCompanies]
        output = [] 
        
        for i in range (len(sets)):
            superset = True
            for j in range(len(sets)):
                if i == j: continue
                if sets[i].issubset(sets[j]):
                    superset = False
                    break
            if superset:
                output.append(i)
                
        return output

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        res=[]
        comp_dict={i:set(v) for i,v in enumerate(favoriteCompanies)}
        for i in range(len(favoriteCompanies)):
            subset=True
            for j in range(len(favoriteCompanies)):
                if i==j:
                    continue
                if not comp_dict[i]-comp_dict[j]:
                    subset=False
                    break
            if subset:
                res.append(i)
        return res         
                
       


class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        ans = []
        d = {i : set(favoriteCompanies[i]) for i in range(len(favoriteCompanies))}
        for i in range(len(favoriteCompanies)):
            for j in range(len(favoriteCompanies)):
                if i != j:
                    if not d[i] - d[j]:
                        break
            else:
                ans.append(i)
                
        return ans
        


class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        
        def judge(i):
            for j in range(n):
                if i != j:
                    contain = True
                    for x in favoriteCompanies[i]:
                        if x not in favoriteCompanies[j]:
                            contain = False
                            break
                    if contain:
                        return False
            return True
        
        n = len(favoriteCompanies)
        favoriteCompanies = list(map(set,favoriteCompanies))
        res = []
        for i in range(n):
            if judge(i): res.append(i)
        return res


class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        d = {i: set(v) for i, v in enumerate(favoriteCompanies)}
        print(d)
        res = []
        for i in range(len(favoriteCompanies)):
            subSet = True
            for j in range(len(favoriteCompanies)):
                if i == j:
                    continue
                if not d[i] - d[j]:
                    subSet = False
                    break
            if subSet: res.append(i)         
        return res    

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        hms = []
        output = []
        
        for favs in favoriteCompanies:
            hm = set(favs)
            hms.append(hm)
        
        for i in range(len(favoriteCompanies)):
            good = True
            for j in range(len(favoriteCompanies)):
                if i == j:
                    continue
                z = hms[j].intersection(hms[i])
                if z == hms[i]:
                    good = False
            if good:
                output.append(i)
        
        return output

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        n = len(favoriteCompanies)
        favoriteCompanies = [set(elem) for elem in favoriteCompanies]
        
        ans = []
        for i in range(n):
            not_subset = True
            for j in range(n):
                if i == j:
                    continue
                if len(favoriteCompanies[i] - favoriteCompanies[j]) == 0:
                    not_subset = False
                    break
            if not_subset:
                ans.append(i)
        return ans

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        name_to_index = {}

        company_indices = []
        for _ in favoriteCompanies:
            indices = []
            for name in _:
                if name not in name_to_index:
                    name_to_index[name] = len(name_to_index)
                indices.append(name_to_index[name])
            print(indices)
            company_indices.append(set(indices))
        print(\"-\" * 10)

        ret = []
        for ix, x in enumerate(company_indices):
            valid = True
            for iy, y in enumerate(company_indices):
                if ix == iy:
                    continue
                if x.union(y) == y:
                    valid = False
                    break
            if valid:
                ret.append(ix)
        return ret


class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        ans = [x for x in range(len(favoriteCompanies))]
        for i in range(len(favoriteCompanies)):
            for j in range(i+1,len(favoriteCompanies)):
                set1 = set(favoriteCompanies[i])
                set2 = set(favoriteCompanies[j])
                if set1.issubset(set2):
                    ans[i] = -1
                elif set2.issubset(set1):
                    ans[j] = -1
        return [x for x in ans if x >=0]

class Solution:
    def peopleIndexes(self,favoriteCompanies):
        responses = dict()
        ret = []
        for i in range(len(favoriteCompanies)):
            responses[i] = set(favoriteCompanies[i])
        
        for i, resp in list(responses.items()):
          not_sub = True
          for v in list(responses.values()):
            if resp == v:
              continue
            if resp - v == set():
              not_sub = False
          if not_sub:
            ret.append(i)
        
        return list(sorted(ret))
            
                    


class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        fav = []
        for f in favoriteCompanies:
            fav.append(set(f))

        n = len(favoriteCompanies)
        rem = set()

        for i in range(n):
            for j in range(i+1, n):
                if not fav[i] - fav[j]: # then i is a subset of j
                    rem.add(i)
                if not fav[j] - fav[i]:
                    rem.add(j)

        res = []
        for i in range(n):
            if i not in rem:
                res.append(i)

        return res

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        
        fcs = [set(fc) for fc in favoriteCompanies]
        
        ret = []
        
        for i in range(len(fcs)):
            to_incl = True            
            for j in range(len(fcs)):
                if j != i and fcs[i].issubset(fcs[j]):
                    to_incl = False
                    break
            if to_incl:
                ret.append(i)
        return ret
            


class Solution:
    def peopleIndexes(self, A: List[List[str]]) -> List[int]:
        d = {i: set(v) for i, v in enumerate(A)}
        res = []
        for i in range(len(A)):
            isSubset = False
            for j in range(len(A)):
                if i == j:
                    continue
                if not d[i] - d[j]:
                    isSubset = True
                    break
            if not isSubset: res.append(i)         
        return res    

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        d={i: set(v) for i,v in enumerate(favoriteCompanies) }
        ans=[]
        n=len(favoriteCompanies)
        for i in range(n):
            subSet=True
            for j in range(n):
                if i==j:
                    continue
                if not d[i]-d[j]:
                    subSet=False
                    break
            if subSet:
                ans.append(i)
        return ans


class Solution:
    def peopleIndexes(self, A: List[List[str]]) -> List[int]:
        d = {i: set(v) for i, v in enumerate(A)}
        res = []
        for i in range(len(A)):
            subSet = True
            for j in range(len(A)):
                if i == j:
                    continue
                if not d[i] - d[j]:
                    subSet = False
                    break
            if subSet: res.append(i)         
        return res

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        sol = []
        
        for i, curr_comps in enumerate(favoriteCompanies):
            curr_comps = set(curr_comps)
            is_subset = False
            
            for j, other_comps in enumerate(favoriteCompanies):
                if j == i:
                    continue
                    
                other_comps = set(other_comps)
                    
                if curr_comps.issubset(other_comps):
                    is_subset = True
            
            if not is_subset:
                sol.append(i)    
        
        return sol

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        ans = []
        for i in range(0, len(favoriteCompanies)): 
            setLst = set(favoriteCompanies[i])
            flag = False
            for j in range(0, len(favoriteCompanies)):
                if j == i:
                    continue 
                if setLst.issubset(set(favoriteCompanies[j])):
                    flag = True
                    break;
            if flag == False:
                ans.append(i)
        return ans
                    
                


class Solution:
    def peopleIndexes(self, A: List[List[str]]) -> List[int]:
        d = {i: set(v) for i, v in enumerate(A)}
        res = []
        for i in range(len(A)):
            subSet = True
            for j in range(len(A)):
                if i == j:
                    continue
                if not d[i] - d[j]:
                    subSet = False
                    break
            if subSet: res.append(i)         
        return res    

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        # make companies -> person dict
        # for each person, find if the don't have a subset
        ans = []
        favorites = defaultdict(list)
        for i, person in enumerate(favoriteCompanies):
            for company in person:
                favorites[company].append(i)
        
        for i, person in enumerate(favoriteCompanies):
            possible_supersets = set(range(len(favoriteCompanies)))
            possible_supersets.remove(i)
            for companies in person:
                possible_supersets = possible_supersets.intersection(set(favorites[companies]))
                if len(possible_supersets) == 0:
                    break
            if len(possible_supersets) == 0:
                ans.append(i)
        return ans

class Solution:
    def isSub(self, s1, s2):
        i = 0
        for j in range(len(s2)):
            if s1[i] == s2[j]:
                i = i + 1
            if i == len(s1):
                return True
        return False
    
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        fc = [(sorted(e), i) for i, e in enumerate(favoriteCompanies)]
        fc = sorted(fc, key=lambda x: len(x[0]), reverse=True)
        # print(fc)
        res = []
        for i in range(len(fc)):
            s, si = fc[i]
            found = False
            for j in range(i):
                ps, sj = fc[j]
                if self.isSub(s, ps):
                    found = True
                    break
            if not found:
                res.append(si)
            
        return sorted(res)


class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        N = len(favoriteCompanies)
        result = list(range(0,N))
        
        for i in range(0,N):
            a = set(favoriteCompanies[i])
            for j in range(0,N):
                if i == j or len(a) > len(favoriteCompanies[j]):
                    continue
                    
                b = set(favoriteCompanies[j])
                if a.intersection(b) == a:
                    result.remove(i)
                    break
                    
        return result


class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        n = len(favoriteCompanies)
        res = list(range(n))
        seen = set()
        for i in range(n-1):
            for j in range(i+1, n):
                first_set = set(favoriteCompanies[i])
                second_set = set(favoriteCompanies[j])
                remind = first_set & second_set
                
                if remind == first_set:
                    if i not in seen:
                        seen.add(i)
                        res.remove(i)
                if remind == second_set:
                     if j not in seen:
                        seen.add(j)
                        res.remove(j)
        return res

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        c = set()
        d = {} 
        i = 0
        com = []
        for j in favoriteCompanies:
            cur = set()
            for x in j:
                if x not in d:
                    d[x] = i; i+=1
                    cur.add(d[x])
                else: cur.add(d[x])
            com += [cur]
        ans = []
        #print(com)
        for i in range(len(com)):
            flag = False
            for j in range(len(com)):
                if i!=j:
                    if com[i].issubset(com[j]):
                        flag = True
                        break
            if not flag: ans += [i]
        return ans 

        


class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        n = len(favoriteCompanies)
        res = list(range(n))
        seen = set()
        for i in range(n-1):
            for j in range(i+1, n):
                if i != j:
                    first_set = set(favoriteCompanies[i])
                    second_set = set(favoriteCompanies[j])
                    remind = first_set & second_set
                    if remind == first_set:
                        if i not in seen:
                            seen.add(i)
                            res.remove(i)
                    if remind == second_set:
                        if j not in seen:
                            seen.add(j)
                            res.remove(j)
        return res


class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        
        compfaves = {}
        
        for i,faves in enumerate(favoriteCompanies):
            for comp in faves:
                if not comp in compfaves:
                    compfaves[comp]=[]
                compfaves[comp].append(i)
        
        outarr=[]
        for i,faves in enumerate(favoriteCompanies):
            
            matches = {}
            for comp in faves:
                for person in compfaves[comp]:
                    if not person in matches:
                        matches[person]=0
                    matches[person]+=1
            # print(i,matches)
            issubset=False
            for p,c in list(matches.items()):
                if len(faves)==c and p!=i:
                    issubset=True
                    break
            if not issubset:
                outarr.append(i)
        return outarr


class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        yu=[]
        for j in range(len(favoriteCompanies)):
            a=favoriteCompanies[j]
            yu1=list(favoriteCompanies)
            yu1.pop(j)
            if any(set(a).issubset(set(ele)) for ele in yu1)== False:
                yu.append(j)
        return yu

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        n = len(favoriteCompanies)
        res = set()
        for i in range(n-1):
            for j in range(i+1, n):
                first_set = set(favoriteCompanies[i])
                second_set = set(favoriteCompanies[j])
                remind = first_set & second_set
                
                if remind == first_set:
                    res.add(i)
                if remind == second_set:
                    res.add(j)
        return sorted(list(set(range(n)) - res))

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        i = 0
        ans = []
        
        while i < len(favoriteCompanies):
            if all(not set(favoriteCompanies[i]).issubset(favoriteCompanies[j]) for j in range(len(favoriteCompanies)) if i!=j): ans.append(i)
            i += 1
       
        return ans

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        return [i for i,s1 in enumerate(favoriteCompanies)
               if not any(set(s1).issubset(s2) for s2 in favoriteCompanies if s1 is not s2)]

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        company = []
        for i, fc in enumerate(favoriteCompanies):
            company.append((tuple(fc), len(fc), i))
        company.sort(key = lambda x: -x[1])
        
        maxlen = company[0][1]
        loc = -1
        res= []
        for i in range(len(company)):
            if company[i][1] == maxlen:
                res.append(company[i][2])
                loc= max(loc, i)
            else: break
        
        for i in range(loc+1, len(company)):
            curr = company[i][0]
            flag = 0
            for j in range(i-1, -1, -1):
                tmpt = company[j][0]
                if set(curr) & set(tmpt) == set(curr): flag = 1
            if flag == 0: res.append(company[i][2])
        return sorted(res)
                
                
                

            


class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        A = favoriteCompanies
        location = {tuple(val):idx for idx, val in enumerate(A)}
        A.sort(key=lambda x: len(x))
        res = []
        for i in range(len(A)):
            for j in range(i+1, len(A)):
                if set(A[i]) & set(A[j]) == set(A[i]):
                    break
            else:
                res.append(location[tuple(A[i])])

        res.sort()    
        return res


class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        # brutal force
        
        return [pid for pid in range(len(favoriteCompanies)) if all((not set(favoriteCompanies[pid]).issubset(s)) for s in [a for a in favoriteCompanies if a != favoriteCompanies[pid]])]