python之检查两个列表在 Python 中是否至少有 2 个共同项目的最快方法

 a={} 
 
 t= list(map(int,input().split())) 
 n=t[0] 
 k=t[1] 
 
 for i in range(n): 
    a.update({i:[]}) 
 
 ids=[]  
 
 for i in range(n): 
     k=input().split() 
     ids.append(set(k[1:])) 
 
 
 def ifrel(i, j): 
    if i==j: 
      return False 
    return len(ids[i] & ids[j]) >= 2 
 
 for i in range(n): 
    for j in range(n): 
       if ifrel(i,j): 
          a[i].append(j) 
 stack=[] 
 res=[] 
 def iterdfs(g,s): 
     stack.append(s) 
     while stack!=[]: 
       k=stack.pop() 
       if k not in res: 
          res.append(k) 
       for i in g[k]: 
          if i not in res:  
         stack.append(i) 
     return res 
 
  print(len(iterdfs(a,0))) 

这是使用 Set 的最终解决方案，但我仍然遇到 TLE!

ids[] 是一个包含列表的列表，例如:ids= [ ['1','2','3']] 。使用Dictionary会提高速度吗？

我在编辑时遇到了一些麻烦，因为这是我在 Stack Overflow 中的第一个问题。

我要解决的问题是: https://www.codechef.com/IOIPRAC/problems/INOI1302/

请您参考如下方法:

如果您想要最快 的解决方案，它不会很简洁。这是最坏情况 O(A + B) 的尝试，但一旦找到两个匹配项就会退出，最好情况 Ω(B)，其中 B 是两个列表中较短的一个。

def check_common_items(A, B, n=2): 
 
    # set B to be the shorter list, len is O(1) 
    if len(B) < len(A): 
        A, B = B, A 
 
    B_set = set(B) # O(len(B)) 
 
    count = 0 
    for a in A: # worst case O(len(A)) 
        if a in B_set: # O(1) 
            count += 1 
            if count == n: 
                return True 
    return False 

但是，大多数使用集合的实现都是渐近有效的。例如，以下函数可能不会慢太多。

def check_common_items(A, B, n=2): 
    return len(set(A) & set(B)) >= n