0

我有朋友的名字，我正在寻找朋友的三角形，如果有的话。示例（彼此相邻的名称归类为朋友，在第一行中，第一个数字代表人数，第二个数字代表友谊数）：

6 7
mirko slavko
slavko janko
janko mirko
slavko luka
luka mirjana
mirjana ivana
ivana luka

在这个例子中，janko - mirko - slavko 是一个三角形，mirjana - luka - ivana 是另一个三角形。

我写了一个代码，它生成一个代表这个图的二维列表。

L = [input().split() for i in range (n)]
H=[]
for i in range(n):
    for j in range(2):
        if L[i][j] not in H:
            H.append(L[i][j])
H.sort()

for number, name in enumerate(H):
    for i in range (n):
        for j in range(2):
            L[i][j]=L[i][j].replace(name, str(number))
        
    
matrix = [[0 for i in range(m)] for j in range(m)]

for i, j in L:
    matrix[int(i)][int(j)]=matrix[int(j)][int(i)]=1

图形是这样的（名字按字母顺序排列，每一行每一列代表一个名字，1代表有友谊，0代表这两个人不是朋友）：

[0, 0, 1, 1, 0, 0]  
[0, 0, 0, 0, 1, 1]  
[1, 0, 0, 1, 0, 1]  
[1, 0, 1, 0, 0, 0]  
[0, 1, 0, 0, 0, 1]  
[0, 1, 1, 0, 1, 0]

我的问题是如何找到带有代码的三角形？

4

2 回答 2

0

最简单的方法是

  1. 创建一个字典，其键是人名，值是该人的朋友集。确保如果 A 在 B 的朋友集中，则 B 也在 A 的朋友集中。

  2. 对于每一对A人和B，看是否friends[A].intersect(friends[B])为空。

于 2021-10-15T20:25:05.713 回答
0

大多数形式的团问题都是困难的，最一般的解决方案是 NP 完全的。因此 O(N**3) 可能是您可以做的最好的假设输入表示是有效的，并且由于您已经制作了 2d 矩阵，所以您大部分时间都在那里。

friends = [
     [0,1,1,0],
     [1,0,1,1],
     [1,1,0,0],
     [0,1,0,0]]
n = 4

for i in range(n):
    for j in range(i+1, n):
        if not friends[i][j]:
            continue
        for k in range(j+1, n):
            if friends[i][k] and friends[j][k]:
                print('friends!')
                print(i,j,k)
于 2021-10-15T20:44:35.003 回答