問題タブ [kosaraju-algorithm]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
kosaraju-algorithm - Regex pattern in JavaScript to test for dots/hyphens in names
Required regex pettern like
- allow only letters with min 1 dot and maximum 3 dots.
- allow optional as '-' special character.
Ex: raj.gopal-reddy or raj.reddy.gopal
c++ - 同様に記述されたコードがはるかに高速に実行されるのに、私の C++14 KosaRaju アルゴが TLE になるのはなぜですか
TLE コードは 2.1 秒で完了します。また、参照を介して多くのものを渡していますが、まだ TLE をスローしています。このコードはなぜそんなに時間がかかるのですか?
ハッカーアースの問題は次のとおりです。
https://www.hackerearth.com/problem/algorithm/falling-dominos-49b1ed46/
ドミノはとても楽しいです。子供たちは、タイルを横に並べて長い列に並べるのが好きです。1 つのドミノが倒れると、次のドミノが倒され、次のドミノが最後まで倒されます。ただし、ドミノが次のドミノを倒せないことがあります。その場合、ドミノを再び落下させるには、手で倒さなければなりません。あなたの仕事は、与えられたいくつかのドミノ タイルのレイアウトから、すべてのドミノを倒すために手で倒さなければならないドミノの最小数を決定することです。
入力
入力の最初の行には、追跡するテスト ケースの数を指定する 1 つの整数が含まれます。各テスト ケースは、それぞれが 100 000 を超えない 2 つの整数を含む行で始まります。最初の整数 n はドミノ タイルの数で、2 番目の整数 m はテスト ケースで続く行の数です。ドミノ牌には 1 から n までの番号が付けられています。次の各行には、x と y の 2 つの整数が含まれており、ドミノ番号 x が倒れるとドミノ番号 y も倒れることを示しています。
出力
テスト ケースごとに、1 つの整数を含む行を出力します。これは、すべてのドミノを倒すために手で倒さなければならないドミノの最小数です。
サンプル入力 1 3 2 1 2 2 3 サンプル出力 1
コードは 2.1 で完成
Efficient Code は 0.7 秒で完了します。
c++ - kosaraju アルゴリズムが機能する理由とその背後にあるアイデアは何ですか?これは正しい実装ですか?
なぜグラフの転置を作成し、2 番目のパスで転置に対して dfs を実行するのでしょうか。正しさの証明http://www.jeffreykarres.com/blog/kosaraju/をオンラインで読んでみましたが、理解できませんでした。これを行うには、理解しやすい代替アプローチがいくつかあります
これはアルゴリズムの私の実装であり、入力として頂点とエッジの数を取り、次に有向エッジを入力として取ります（頂点には0からn-1の番号が付けられます）