在图中寻找特殊的边

Question

我有一个无向图，它有一定数量的节点和边。

每个节点都有一定的颜色，每一个边缘都是特定类型的，这取决于它连接到的节点的颜色：

• 连接红色和蓝色节点的边缘是红色-蓝色的.
• 因为图是无向的：red-blue == blue-red。

我的任务是编写算法，以找到所有的边缘是“孤立的”。

当原始边缘与与原始边缘类型相同的下一边缘之间至少有2条边缘距离时，边缘被隔离。

做这件事最好的方法是什么？它很可能可以使用广度/深度优先搜索来解决，但我无法找到将它们与这个特定问题联系起来的方法。

Answer 1

我很确定这会起作用，不确定复杂程度。

For each node n:
    For each edge (n, n2) e:
        n.colors[edgeColor(e)] += 1
For each node n:
    n.colors2 = n.colors.copy()
    For each edge (n, n2) e:
        n.colors2 = mergeSum(n.colors2, n2.colors)
For each edge (n, n2) e:
   if n.colors2[edgeColor(e)] == 2 and n2.colors2[edgeColor(e)] == 2:
       isolated edge