2

私は試験のために学んでいますが、この問題に対処できません:

n <= 300 000 ノードのグラフが与えられますが、圧縮形式です。この形式は、m <= 300 000 行で構成され、それぞれが a_i、b_i、c_i の 3 つの数値で指定されます。これは、ノード 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

答えはイエスです (例えば、サイクル: 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 に答える