プログラミング

有名なゲーム「蛇と梯子」について知っています。このゲームでは、いくつかの部屋が部屋番号とともにボード上に存在します。一部の客室ははしごやヘビでつながっています。はしごを手に入れると、順番に移動することなく、目的地の近くに到達するためにいくつかの部屋に登ることができます。同様に、ヘビを捕まえると、下の部屋に送られ、その部屋から旅を再開します。 この問題では、開始から目的地に到達するために必要なサイコロの投げの最小数を見つける必要があります。 入力と出力 Input: The starting and ending location of the snake and ladders. Sn

Tarjanのアルゴリズムは、有向グラフの強連結成分を見つけるために使用されます。このアルゴリズムを実装するために必要なDFSトラバーサルは1つだけです。 DFSトラバーサルを使用して、フォレストのDFSツリーを見つけることができます。 DFSツリーから、強く接続されたコンポーネントが見つかります。そのようなサブツリーのルートが見つかると、サブツリー全体を表示できます。そのサブツリーは、1つの強連結成分です。 入力と出力 Input: Adjacency matrix of the graph. 0 0 1 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0

有向非巡回グラフのトポロジカルソートは、頂点の線形順序付けです。有向グラフのすべてのエッジU-Vについて、頂点uは順序付けで頂点vの前に来ます。 ソース頂点はデスティネーション頂点の後に来ることがわかっているので、スタックを使用して前の要素を格納する必要があります。すべてのノードが完成したら、スタックからノードを表示するだけです。 入力と出力 Input: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 Output: Nodes after topological sorted orde

Ford-Fulkersonアルゴリズムは、特定のグラフの開始頂点からシンク頂点への最大フローを検出するために使用されます。このグラフでは、すべてのエッジに容量があります。 SourceとSinkという名前の2つの頂点が提供されます。ソース頂点にはすべて外向きのエッジがあり、内向きのエッジはありません。シンクにはすべて内向きのエッジがあり、外向きのエッジはありません。 いくつかの制約があります： エッジのフローは、そのグラフの所定の容量を超えません。 流入フローと流出フローも、ソースとシンクを除くすべてのエッジで等しくなります。 入力と出力 入力：隣接行列：0 10 0 10 0

推移閉包グラフの頂点uから頂点vに到達する到達可能性マトリックス。 1つのグラフが与えられ、すべての頂点ペア（u、v）について、別の頂点uから到達可能な頂点vを見つける必要があります。 最終的な行列はブール型です。頂点uから頂点vに値1がある場合、それはuからvへのパスが少なくとも1つあることを意味します。 入力と出力 Input: 1 1 0 1 0 1 1 0 0 0 1 1 0 0 0 1 Output: The matrix of transitive closure 1 1 1 1 0 1 1 1 0 0 1 1 0 0 0 1 アルゴリズム transColsure

グラフが表示されます。与えられたグラフがスターグラフであるかどうかを確認する必要があります。 グラフをトラバースすることにより、次数が1の頂点の数と次数がn-1の頂点の数を見つける必要があります。 （ここで、nは与えられたグラフの頂点の数です）。次数1の頂点の数がn-1で、次数（n-1）の頂点の数が1の場合、それはスターグラフです。 入力と出力 Input: The adjacency matrix: 0 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0 Output: It is a star graph. アルゴリズム checkStarGraph(graph) 入力

ベルマンフォードアルゴリズムは、ソース頂点から他の頂点までの最小距離を見つけるために使用されます。このアルゴリズムとダイクストラのアルゴリズムの主な違いは、ダイクストラのアルゴリズムでは負の重みを処理できないことですが、ここでは簡単に処理できます。 Bellman-Fordアルゴリズムは、ボトムアップ方式で距離を検出します。最初に、パスにエッジが1つしかない距離を見つけます。その後、パスの長さを増やして、考えられるすべての解決策を見つけます。 入力と出力 Input: The cost matrix of the graph: 0  6  ∞ 7 &n

この問題では、さまざまなボックスのセットが提供されます。長さ、幅、幅はボックスごとに異なる場合があります。私たちの仕事は、これらの箱の積み重ねを見つけることです。その高さは可能な限り高くなっています。好きなようにボックスを回転させることができます。ただし、維持するルールがあります。 下のボックスの上面の面積が上のボックスの下部の面積よりも大きい場合は、別のボックスにボックスを配置できます。 入力と出力 Input: A list of boxes is given. Each box is denoted by (length, bredth, height). { (4, 6, 7), (

無向グラフにサイクルがあるかどうかを検出するために、指定されたグラフのDFSトラバーサルを使用します。訪問した頂点vごとに、隣接する頂点uが見つかった場合、uはすでに訪問されており、uは頂点vの親ではありません。その後、1サイクルが検出されます。 頂点のペアには平行なエッジがないと仮定します。 Input and Output: Adjacency matrix         0 1 0 0 0     1 0 1 1 0     0 1 0 0 1     0 1 0 0 1 &n

深さ優先探索（DFS）トラバーサルアルゴリズムを使用して、有向グラフでサイクルを検出できます。いずれかのノードに自己ループがある場合、それはサイクルと見なされます。そうでない場合、子ノードに親を接続するための別のエッジがある場合、それもサイクルになります。 切断されたグラフの場合、異なる木が存在する可能性があり、それらを森と呼ぶことができます。次に、森のすべての木の周期を検出する必要があります。 このアプローチでは、さまざまなセットを使用して、DFSトラバーサルを実行するノードを割り当てます。ホワイト、グレー、ブラックの3つのセットがあります。最初は、すべてのノードがホワイトセット内

オイラーパスは、すべてのエッジを1回だけ訪問できるパスです。同じ頂点を複数回使用できます。オイラー回路は、特殊なタイプのオイラーパスです。オイラーパスの開始頂点がそのパスの終了頂点にも接続されている場合、それはオイラー回路と呼ばれます。 グラフがオイラーであるかどうかを確認するには、2つの条件を確認する必要があります- グラフを接続する必要があります。 各頂点の次数と次数は同じである必要があります。 入力と出力 Input: Adjacency matrix of the graph. 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 0

オイラーパスは、すべてのエッジを1回だけ訪問できるパスです。同じ頂点を複数回使用できます。オイラー回路は、特殊なタイプのオイラーパスです。オイラーパスの開始頂点がそのパスの終了頂点にも接続されている場合、それはオイラー回路と呼ばれます。 パスと回路を検出するには、次の条件に従う必要があります- グラフを接続する必要があります。 ちょうど2つの頂点の次数が奇数の場合、それはオイラーパスです。 無向グラフの頂点の次数が奇数でない場合、それはオイラー回路です。 入力と出力 Input: Adjacency matrix of a graph. 0 1 1 1 0 1 0 1 0 0 1

フルーリーのアルゴリズムは、特定のグラフからオイラーパスまたはオイラー回路を表示するために使用されます。このアルゴリズムでは、1つのエッジから開始して、前の頂点を削除することにより、他の隣接する頂点を移動しようとします。このトリックを使用すると、オイラー経路または回路を見つけるための各ステップでグラフが簡単になります。 パスまたは回路を取得するには、いくつかのルールを確認する必要があります- グラフはオイラーグラフである必要があります。 2つのエッジがあり、1つはブリッジ、もう1つは非ブリッジの場合、最初に非ブリッジを選択する必要があります。 開始頂点の選択も注意が必要です

グラフ彩色の問題は、グラフラベリングの特殊なケースです。この問題では、各ノードがいくつかの色に色分けされています。しかし、着色にはいくつかの制約があります。隣接する頂点に同じ色を使用することはできません。 この問題を解決するには、欲張りアルゴリズムを使用する必要がありますが、最小色を使用することを保証するものではありません。 入力と出力 入力：グラフの隣接行列0 0 1 0 10 0 1 1 11 1 0 1 00 1 1 0 11 1 0 1 0出力：ノード：0、色で割り当て：0ノード：1、色で割り当て：0ノード：2、色で割り当て：1ノード：3、色で割り当て：2ノード：4、色で割り当

加重有向非巡回グラフが1つ示されています。別のソース頂点も提供されます。次に、グラフで、開始ノードから他のすべての頂点までの最長距離を見つける必要があります。 トポロジカルソート手法でノードをソートする必要があり、トポロジカルソート後の結果はスタックに格納されます。その後、スタックから繰り返しポップし、各頂点の最長距離を見つけようとします。 入力と出力 Input: The cost matrix of the graph. 0  5   3 -∞ -∞ -∞ -∞ 0   2  6 -&in

グラフのすべてのエッジが最初のセットから始まり、で終わるように、グラフの頂点を2つの独立したセットに分割できる場合、グラフは2部グラフと呼ばれます。 2番目のセット、または最初のセットに接続された2番目のセットから開始します。つまり、同じセットにエッジが見つからないと言うことができます。 頂点カラーリングを使用することにより、2部グラフのチェックが可能です。頂点が同じセットにある場合、同じ色になります。別のセットの場合、色が変わります。 入力と出力 Input: The adjacency matrix. 0 1 1 1 0 0 1 0 0 1 1 0 1 0 0 1 0 1 1

加重有向非巡回グラフが1つ示されています。別のソース頂点も提供されます。次に、グラフで開始ノードから他のすべての頂点までの最短距離を見つける必要があります。 より短い距離を検出するには、負の重みを持つグラフにベルマンフォードのよ​​うな別のアルゴリズムを使用できます。正の重みには、ダイクストラのアルゴリズムも役立ちます。ここでは、有向非巡回グラフについて、トポロジカルソート手法を使用して複雑さを軽減します。 入力と出力 Input: The cost matrix of the graph. 0   5  3 -∞ -∞ -∞ -

2部マッチングとは、グラフ内のエッジのセットが、そのセット内の2つのエッジがエンドポイントを共有しないように選択されることです。最大一致は、エッジの最大数と一致しています。 最大の一致が見つかった場合、別のエッジを追加することはできません。最大一致グラフに1つのエッジが追加されると、それは一致しなくなります。 2部グラフの場合、最大マッチングが複数存在する可能性があります。 入力と出力 Input: The adjacency matrix. 0 1 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1

この問題では、n点のセットが2D平面上に与えられます。この問題では、距離が最小の点のペアを見つける必要があります。 この問題を解決するには、ポイントを2つに分割する必要があります。その後、2つのポイント間の最小距離が再帰的に計算されます。中央の線からの距離を使用して、ポイントはいくつかのストリップに分割されます。ストリップ配列からの最小距離を見つけます。最初に2つのリストがデータポイントで作成されます。1つのリストはx値で並べ替えられたポイントを保持し、もう1つはy値で並べ替えられたデータポイントを保持します。 このアルゴリズムの時間計算量はO（n log n）になります。 入力と出力 I

アイテムは、その要素の4つの隣接要素すべて以上である場合、ピーク要素であると言われます。隣接する要素は、上、下、左、右の要素です。この問題については、いくつかの限界を検討します。対角要素は隣接要素としてチェックされません。マトリックス内に複数のピーク要素が存在する場合があり、ピーク要素は必ずしもマトリックス内で最大の要素であるとは限りません。 入力と出力 Input: A matrix of different numbers. 10  8  10  10 14 13  12  11 15  9  11  11 1