2

我正在为考试而学习，但无法解决这个问题：

我们得到一个 n <= 300 000 个节点的图，但是是压缩形式的。这种形式由 m <= 300 000 行组成，每行由三个数字给出：a_i, b_i, c_i，这意味着从节点 a_i 到区间 [b_i, c_i] 内的所有节点都有有向边。问题是确定给定图中是否存在循环。

例如输入：（数字 n，m，然后是描述图形的 m 行）

4 5

1 2 3

1 4 4

2 3 4

3 4 4

4 1 1

答案是YES（例如循环：1->2->3->4->1）

对于这个输入：

4 4

1 2 3

1 4 4

2 3 4

3 4 4

答案是不。

所以主要的问题是这个图可能真的很大，我负担不起创建它和运行 DFS。它必须做得更快。我的第一个想法是使用拓扑排序算法。如果它有效，则给定图中没有循环，否则存在循环。但是更新节点的度数很困难（为了在该算法的每一步中选择deg_in = 0的节点）。我在想也许使用区间树会有所帮助 - 当我删除节点 v 时，我可以看到他的邻接列表（这个列表的元素将被赋予间隔）并且对于所有间隔递减这些点的 deg_in。所以我可以在对数时间内检查节点度数是多少，但我仍然无法快速更新 deg_in = 0 的节点列表。我不知道，也许我正在尝试一个无法修复的解决方案？

有人可以帮忙吗？

4

1 回答 1

0

我将尝试为该算法制作一个元代码。这将是图旅行算法的一个特例。专长是关于生产线的包装存储。

// Outer loop to check all nodes
CheckedNodes = (empty)
for n1 in 1 .. n {
    if (not(CheckedNodes contains n1)) {
        add n1 to CheckedNodes
        VisitedNodes = (empty) // initialization
        VisitableNodes = { n1 } // start the walk from here
        // Inner loop to walk through VisitableNodes
        While (VisitableNodes is not empty) {
            n2 := select one from VisitableNodes
            remove n2 from VisitableNodes
            add n2 to CheckedNodes // this will stop processing again
            for all lines starting from n2 { // we add all points for all lines
                for n3 in line.start .. line.end { 
                    if (VisitedNodes contains n3) { 
                        // we found an already visited node
                        return "Circle found in Graph!" 
                    } else {
                        // otherwise we should visit that later
                        add n3 to VisitableNodes
                    }
                }
             }
        }
    }
}
// we have not found a circle
return "No circle found in Graph!"

问题是执行。在我使用集合的算法中CheckedNodes，VisitedNodes它们 - 带有整数索引 - 可以通过布尔数组（或类似的东西）轻松实现。这VisitableNodes是一个列表，它应该由一个类似列表的结构来实现。

于 2013-01-12T00:49:50.527 回答