Tarjan強連通成分アルゴリズムの理解

Tarjan強連通成分アルゴリズムの理解
今日はつまらなくて図论の复习を始めました.私のような板を书くのがあまり好きではないこんにゃくにとって、やっとTarjanの强い连通アルゴリズムに戻るつもりです.
まず、Tarjanアルゴリズムの原理を示します.
げんり
Tarjanのアルゴリズムは主にDFSツリーに基づいており,基本と求点双,辺双などの差は多くない.DFSツリーの場合、DFSツリーと呼ばれているため、DFSシーケンスに従って遍歴しているに違いありません.このとき,lowlinkという配列を記録し,lowlonk[x]にとって,このDFSツリー上でxと番号付けされたノードが達成できる最も早いノードを記録した.
一番早いノードとは何ですか?これは時間で測らなければならない.タイム・スライスは、あるノードxにアクセスした時間(またはxはDFSシーケンスのいくつか目)を記録し、このアルゴリズムではアクセスしたばかりの時間を記録し、配列pre[]で記録します.離れる時間は記録されていません(この2つの違いは、アクセスしたばかりのときに後続ノードにアクセスしていないこと、すなわち、次のDFSがまだ行われていないこと、離れたときにこのノードの後続ノードにアクセスしていないことです.この2つの時間は、ツリー・セグメントおよびそのメンテナンス・サブツリー情報の操作によく使用されます.詳細は、ツリー・セグメントに関する資料を参照してください).
次に、xの後続ノードおよびDFSツリー上の逆エッジが指すノード(逆エッジ、すなわち非ツリーエッジ、原図には存在するがDFSシーケンスの理由でDFSツリー上に現れないエッジ)のlowlinkを使用してxのlowlinkを更新するたびに、ここではmin()関数を使用する必要があります.lowlinkが小さいほどアクセス時間が早いためです.
最後に、pre[x]=lowlink[x]を満たすノードxを考慮すると、最も早く到着したノードはそれ自身であることを示します.では、それとその後継者たちは同じ強い連通成分にある(実際には、ここでは厳密ではなく、xノードの特定の後継者を意味し、そのいくつかの後継者が強い連通成分に属していると判断された場合、この後継者は計算されない).これにより,すべての強い連通成分を求めた.アルゴリズムにはまだ詳細がたくさんありますが、後述します.
まず本人の醜いコードを貼り付けます(コードの中でlow==lowlink):
Tarjanアルゴリズムテンプレート

vector<int> geo[maxn];
stack<int> scc;
bool vis[maxn];
int sccno[maxn],low[maxn],pre[maxn];
int time=0,cnt=0;
int Tarjan(int x){
    pre[x]=low[x]=++time;
    scc.push(x);
    vis[x]=true;
    for(int i=0;iint op=geo[x][i];
        if(!vis[op]){
            low[x]=min(low[x],Tarjan(op));
        }else if(!sccno[op]){
            low[x]=min(low[x],pre[op]);
        }
    }
    if(low[x]==pre[x]){
        int op=scc.top();
        scc.pop();
        ++cnt;
        while(op!=x){
            sccno[op]=cnt;
            op=scc.top();
            scc.pop();
        }
        sccno[x]=cnt;
    }
    return low[x];
}

詳細
我慢できずにスロットを吐いて、markdownのシーケンステーブルの機能があって本当に腐ってだめです

新しいノードにアクセスするときにlowlink値をpre値に初期化するとともに、このポイントをスタックに押し込み、アクセス(この上に穴が開いているはずの数)

を記録します.

の判断では、pre値を使用してlowlink値との比較を行いますが、timeを使用することはできません.これはtimeが各地を泳いでいるため、すでに元の彼ではありません.

上記のコードの15行目では、反対側のノードのpre値を使用して更新しましたが、なぜlowlink値を使用しないのでしょうか.実はすべてできて、どうせあのノードに戻る时求めるべきなのはすべてすでに求めて、しかしpre値はそれは更に安定して、それはずっとその値の

です

また、逆エッジの他端のノードにラベルが付けられているかどうかを判断するには、なぜですか(コード14行目).これは、それが符号化されている場合、そのノードが現在のノードと同じ研究中のサブツリー(DFSツリーに対して)ではなく、そのブランチが以前からDFSによって到着していたことを示すためである.どうしてラベルがなくてもいいのですか?これは別の分岐に属する点であり,すでに研究されていれば,SCCに1つの点

しかないとしても,必ず番号が付けられているからである.
まとめ
コードが长くなくて、理解するのは难しくなくて、いつも使うわけではありませんが(DPに対して、数学などは)、できたほうができないよりはましです.
例題
私は他の文章を書くかもしれないので、ここに穴を残して補充して、後でリンクします.実はこれらの问题も难しくありません...いくつか挙げておきましょう
スパイネットワーク
タイトルの説明
外国のスパイが大量に浸透したため、国家安全保障は高度な危機に直面している.AスパイがBスパイに関する犯罪証拠を手にしていれば、AはBを摘発できると主張する.一部のスパイは賄賂を受け取って、彼らに一定の数のドルを与えれば、彼らは手に持っているすべての情報を渡したいと思っています.だから、もし私たちがスパイを買収することができたら、私たちはスパイ網の中のすべての分子を制御することができます.私たちがスパイを逮捕したら、彼が持っている情報はすべて私たちの所有になるので、新しいスパイを逮捕して、新しい情報を掌握する可能性があります.
私たちの反スパイ機関は、既知の収賄を受けたすべてのスパイと、彼らが受け取りたい具体的な金額を含む資料を提供した.同時に、どのスパイがどのスパイの資料を具体的に把握しているかも知っています.合計n個のスパイ(nは3000を超えない)が存在すると仮定し、各スパイはそれぞれ1〜3000の整数で識別される.
この資料に基づいて、私たちがすべてのスパイをコントロールする可能性があるかどうかを判断してください.できれば、私たちが支払う最低限の資金を求めてください.そうでなければ、出力は制御できないスパイです.
にゅうしゅつりょくけいしき
入力形式:
最初の行には整数nが1つしかありません.
2行目は整数pです.買収されたい人数を表し、1≦p≦n.
次のp行は、行ごとに2つの整数があり、最初の数は買収されたいスパイの番号で、2番目の数は彼が買収される金額を示しています.この金額は20000を超えない.
1行に1つの整数rしかありません.1≦r≦8000です.そしてr行は、行ごとに2つの正の整数で、数対(A,B)を表し、AスパイがBスパイの証拠を握っている.
出力フォーマット:
すべてのスパイを制御できる場合、第1行はYESを出力し、第2行は支払うべき賄賂の最小値を出力します.そうでなければNOを出力し、2行目に制御できないスパイのうち、番号が最も小さいスパイ番号を出力する.
入出力サンプル
入力サンプル
【サンプル1】3 2 1 10 2 100 2 1 3【サンプル2】4 2 1 100 4 200 2 1 3 4
出力サンプル:
【サンプル1】YES 110【サンプル2】NO 3
これは洛谷の問題です...
[HAOI 2006]人気牛
タイトルの説明
どの乳牛も牛小屋のスターになることを夢見ている.すべての乳牛に好かれる乳牛はスターの乳牛だ.すべての乳
牛はすべてナルシストで、すべての乳牛はいつも自分のことが好きです.乳牛同士の「好き」は伝わる——A喜
Bが好きで、BはCが好きで、それではAもCが好きです.牛の柵の中で共にN頭の乳牛があって、いくつかの乳牛の間の愛慕関係を与えて、どうぞ
どのくらいの乳牛がスターになれるかを計算します.
入力形式:
1行目:スペースで区切られた2つの整数:NとM
2行目からM+1行目:行ごとに2つのスペースで区切られた整数:AとB、AがBが好きであることを示す
出力フォーマット:
1行目:スター乳牛の数を表す整数
入出力サンプル
サンプル#1を入力:
3 3 1 2 2 1 2 3
出力サンプル#1:
1
説明
3番の乳牛だけがスターになれる
データ範囲
10%のデータN<=20,M<=50
30%のデータN<=1000,M<=20000
70%のデータN<=5000,M<=50000
100%のデータN<=10000,M<=50000
これは洛谷の上の問題です...