查找集合列表中数字之间的循环

Question

给定一个集合列表，例如：

sets=[{1,2},{2,3},{1,3}]

乘积

(1,2,3)

将在

itertools.product(*sets)

中生成两次，即文字

(1,2,3)

和

(2,3,1)

，因为存在循环。如果没有循环，就不会有重复，即使集合之间可能有很多共同点。

当您可以从一组中的一个数字移动到该组中的另一个数字，然后移动到另一组中的相同数字并返回到原始数字时，就存在循环，例如

1>2-->2>3-->3>1-->1

其中“-->”表示集合之间的移动，“>”表示集合内的移动。最小的循环将涉及两个集合之间的一对共同数字，例如

a>b-->b>a-->a

。

我可以使用什么类型的图形结构来表示这一点？我尝试将每个集合表示为一个节点，然后指示哪些集合连接到哪个集合，但这并不正确，因为对于

[{1,2},{1,3},{1,4}]

，所有集合之间都有连接（公共 1），但没有循环。我还尝试为每个集合中的每个数字分配一个字母，但这似乎也不正确，从那以后我不知道如何区分集合中的循环within。

Answer 1

• 每个数字都是一个节点。
• 如果数字属于同一集合，则有一条边
• 然后，我们可以使用defaultdict来构建图表。 （如果你有密集的图，你可以在这里构建一个邻接表）。
• 使用深度优先搜索来查找循环。
• 为访问过的节点建立一个访问集并检查每个节点

from collections import defaultdict


def solve(sets):
    def dfs(node, vis, parent):
        vis.add(node)
        for nei in G[node]:
            if nei not in vis:
                if dfs(nei, vis, node):
                    return True
            elif nei != parent:
                return True
        return False

    G = defaultdict(set)
    for s in sets:
        for num in s:
            G[num].update(s - {num})

    vis = set()
    for node in G:
        if node not in vis:
            if dfs(node, vis, None):
                return True

    return False


print(solve([{1, 2}, {2, 3}, {1, 3}]))
print(solve([{1, 2}, {1, 3}, {1, 4}]))

结果

True
False