アルゴリズム概要
本章の主な内容は以下より転載：
核となる考え方は、やはり補強経路を見つけることです。
点の束がマッチしたと仮定すると、マッチしていないノードsから始めて、BFSを使って探索木を生成します。ノードuが見つかるたびに、uがまだマッチしていなければオーグメンテーションに成功し、そうでなければノードuはその仲間vと一緒にツリーに受け取られ、その後vは探索を続けるためにキューに落とされます。探索木の各点に型を与えます：SかTのどちらか。uにT型、vにS型のラベルを付けます。探索木は次のようになります：
実線で結ばれた2点はすでにマッチしており、破線は2点間にエッジがあるがペアになっていないことを示します。オーグメンテーションの過程で、バンダナツリーアルゴリズムはSタイプのノードに対してのみBFSを行います。
ここでちょっとした問題があります。S型の点dが展開のあるステップで点uを発見したとき、uがすでに探索木の中にあったらどうするのか？
uがT型の場合、この発見は無視されます。
そうでない場合は、奇数の長さのリングが見つかった場合、「縮小」操作が実行されます！
いわゆるシュリンク操作とは、リングを点に縮めること。シュリンクポイントの完了後、Tポイント内の元のリングもSポイントに変わり、キューに投げ込まれます。
なぜ1点にできるのですか？奇数の長さの環を見たとき、その環のどの点に対してもアウト度を求めることができれば、環の他の点はちょうど1組になることができ、各点のアウト度は等価であることがわかります。例えば、図の点dにもう1つの仲間を見つけることができるとすると、環の残りの6点はちょうど3組になります。
下図の青い線で示すように、4組のペアができました。
点を縮めるという発想はここから生まれました。あるコンピュータ科学者が、点を縮めることと、縮めた後のグラフが増大パスを持つかどうかが同じであることを証明しました。縮小された点は花とも呼ばれます。花を構成する花の中に，さらに小さな花が入れ子になっていることがあります．
ようやく曾光路を見つけたら、入れ子になっている花の層を広げて、元の絵から曾光路を復元しなければなりません。
なぜ奇数リングを気にして、偶数リングを無視するのですか？
なぜ奇数環にこだわる必要があるのでしょうか？下図のような特異な環があるとします。
図に示すように，S点dに特異リングがある場合の効果を見てみましょう．もしリングがなければ、sはA(s-b-d...)をたどることしかできません。これに対して、sはB(s-a-c-f-j-d...)にも従うことができるようになります。
図のように，T字型の点bに対する特異リングの効果をもう一度見てください．点bと点dはマッチしており、例えばbのマッチしていない他の辺を処理することはなかったでしょう。しかし、リングが持ち込まれたことで、パスCに沿って、エッジを含む補強パスができるようになりました。元々、点bはbfsキューに入っておらず、奇数リング削減フラワーに遭遇した後、bfsキューに追加される必要があります。
要するに、奇数リングの出現によって、奇数リング上の点が、リングのもう半分からオーギュメントされたように見えるのです。この時点で、特異リング上のすべてのT点は、S点となってbfsキューに入ることになります。
偶数リングが無視される理由も、この時点で明らかです。上に示した偶数リングと偶数リングは両方ともマッチしていない辺なので、偶数リング上の点はリングのもう半分に沿って増やすことはできません。
コード詳細
この章のコードは主に
元々はc++でしたが、javaに変更しました。
各変数と配列の意味
int n; //グラフのノード数
List<Integer> e[n]; //e[x]点xとエッジでつながっている他の点は
Queue<Integer> queue; //BFS
int match[n]; //マッチング結果を記録する,match[a] = b a と b がマッチし、両者がmatch[b] = a
char mark[n]; // S/T
int belong[n]; //連結集合を維持する。これは、ある点が同じフラワーに属することを特徴付けるために使用される。
int visit[n]; //LCAでは、ノードがアクセスされたかどうかを記録する。
int next[n]; //オーグメンテーションを行う際には、オーグメンテーションによって生成されたBFS探索木のマッチしていないエッジを記録する。
エッジに関する情報を記録する3つのアレイがあります。
- e[n]：グラフ全体を記録
- match[n]：マッチするエッジを記録
- next[n]：BFS探索木において、増強・拡張時にマッチしなかったエッジを記録
一致しない点からスタートし、増強
void match() {
for (int i = 0; i < n; i++) if (match[i] == -1) aug(i);
}
広げる
/**
* sを始点とするオーグメントパスを見つける
*/
void aug(int s) {
//reset
for (int i = 0; i < n; i++) {
queue.clear();
next[i] = -1;
belong[i] = i;
mark[i] = 0;
}
mark[s] = 'S';
queue.offer(s);
//sがマッチしない場合
int n2 = next[n1];
int n3 = match[n2];
match[n2] = n1;
match[n1] = n2;
n1 = n3;
}
break; // オーグメンテーションが成功し、ループを抜けると次のステージに移る
} else { // y自由ではない、現在の探索のためのクロスチェーン+y+match[y]新しいクロスチェーンの形成はmatch[y]検索されるノードとしてキューに加わる
next[y] = x;
queue.offer(match[y]);
mark[match[y]] = 'S'; // match[y]Sとしてマークされる
mark[y] = 'T'; // yTにマークされる。
}
}
}
}
補強の主な処理は、実はS字ノードのBFSの処理であることがわかります。S字の接続点をトラバースするとき、異なる状況に応じて異なる処理が行われます。
ここでは「クロスチェーン」論法があり、拡大路を見つけるプロセスを指し、マッチするエッジとマッチしないエッジが交互に接続された経路を形成します。
そのうちのいくつかについては、さらに詳しく説明します。
- xとyがマッチ
xは点yのマッチとしてキューに追加されるSノード。xの連結点をトラバースするとき、点yもトラバースされます。
- yはフリーではありません。
xはbにマッチした連結点yにトラバースします。ここでいくつかの操作が行われます。
1) bであるmatch[y]をS型としてマーク；
2) yをT型としてマーク；
3) bを待ち行列に加え、bfsを待ちます；
4) yをxに向け、next[y] = x。
- y free, オーグメンテーション
オーグメンテーション前のサーチツリーの状態を以下に示します。
このコードは、実際には、n1を基点に、次の配列を通ってn2へ、マッチ配列を通ってn3へ、そしてマッチして、最後にn3を新しいn1として、次のラウンドの処理に続きます。
実際、これは探索木の基本構造のようなものです。この基本構造は、縮小フラワーでもLCAでも使われています。
- yはSノード、インデント。縮小はより複雑です。
縮み
一致しないエッジはリングにつながり、探索ツリーは下図のようになります。オレンジ色の線は次の配列によって特定された指し示し関係で、リングに遭遇するまでツリーの下から上を向いていました。
縮小花へのステップ：
- dとjの最も近い共通祖先、ここではsを探しなさい；
- dとjのマッチしないエッジをnextで維持します；
- s --- j
- s --- d
まずLCAを見てみましょう。
/**
* 点xとyの最も近い共通祖先を見つける
*/
int LCA(int x, int y) {
//reset
for (int i = 0; i < n; i++) {
visit[i] = -1;
}
while (true) {
if (x != -1) {
x = findb(x); // 点は花に対応しなければならない
if (visit[x] == 1)
return x;
visit[x] = 1;
if (match[x] != -1) {
x = next[match[x]]; //1つ上のステップを見つける
} else x = -1;
}
//swap x and y
int tmp = x;
x = y;
y = tmp;
}
}
LCAの考え方は、xの先祖を一段階だけ調べ、次にyの先祖を一段階だけ調べるというものです。このように、交互に一段階ずつ上がっていきます。xとyが共通の祖先を持つ場合、xが最初にその祖先を訪れ、次にyが再びその祖先を訪れます。したがって、2回訪れた最初のノードが共通の祖先です。
1ステップのみ」というのは、上で述べたことと関連しています。次の図、x = next[match[x]]は、実際には、n1に従って、n3を取得します。検索ツリーでは、n2の子はn1の1つだけを持っているので、ここでn2をスキップしていることがわかりますが、公の先祖になることはできません。
NEXTのメンテナンスをもう一度見てください。
next[x] = y
next[y] = x
このようにして、マッチ配列と同じように管理されます。
サーチツリーを以下に示します。エッジは切り取られた2本の線で互いに参照されていますが、データ構造としては実はこれと変わりません。
最後にGROUPを見てください。
/**
*
*/
void group(int n1, int s) {
//ループの各ラウンドは、連結集合のルートとしてn3を使用する。
//最終的なn3はsになる。つまり、フラワーを縮小した後、sがそのフラワーのルートとして使用される。
//これは、sがこのツリーにおけるこの花の唯一の連結点であり、その上のノードがLCAで役割を果たすからである。
while (n1 != s) {
int n2 = match[n1], n3 = next[n2];
// _nextフラワー内のパスをマークするために配列が使用され、結合されたマッチ配列は、実際に双方向の連鎖リストを形成するために使用される。
if (findb(n3) != s) next[n3] = n2;
queue.offer(n2);
mark[n2] = 'S'; //n2はS点、n3はT点でなければならない。
unit(n1, n2);
unit(n2, n3); //これらの2つのunit()ステップは、連結されたチェックセットのn1とn2の両方の根をn3
n1 = n3;// ループの次のステップでn3をn1に変更する。
}
}
グループもこの基本構造に基づいて行われます。グループと次の配列のさらなるメンテナンスの過程で、検索ツリー構造の最終的な形成は次のとおりです。
短い
新しいマッチしていない点から補強を試みる場合、その bfs の間に形成された探索木は、match 配列と next 配列を使用して維持されます。next配列がLCAを補助する場合、ノードを後方にトレースするためにグループ化および成功した拡大が使用されます。奇数ループに遭遇した場合、奇数ループは両方のクロック方向で正常に拡張される可能性があるため、nextはmatchと連携して双方向連鎖表を形成します。
フルコード
javaバージョン。ここでの入力と出力は、います。
コードを修正する過程で3つのミスがありました。
- 初期化の際、2つの点のペアが発生し、両方向でマッチを構築する必要があります；
- 新しいマッチしていないポイントを追加するときは、キューを空にする必要があります；
- ビストはLCAごとにRESETしなければなりませんが、オーグごとにRESETするわけではありません。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class Solution {
public static void main(String[] args) throws IOException {
TreeWithBlossomMain treeWithBlossomMain = new TreeWithBlossomMain();
treeWithBlossomMain.init();
treeWithBlossomMain.match();
treeWithBlossomMain.print();
}
static class TreeWithBlossomMain {
int n; //グラフのノード数
List<Integer> e[]; //e[x]点xとエッジでつながっている他の点は
Queue<Integer> queue; //BFS
int match[]; //マッチング結果を記録する,match[a] = b a と b がマッチし、両者がmatch[b] = a
char mark[]; // S/T
int belong[]; //連結集合を維持する。これは、ある点が同じフラワーに属することを特徴付けるために使用される。
int visit[]; //LCAでは、ノードがアクセスされたかどうかを記録する。
int next[]; //オーグメンテーションを行う際には、オーグメンテーションによって生成されたBFS探索木のマッチしていないエッジを記録する。
/**
* stdinから入力を読み込み、グラフを初期化し、配列の領域を確保する。
*/
void init() throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] str = reader.readLine().split(" ");
n = Integer.parseInt(str[0]);
int m = Integer.parseInt(str[1]);
e = new List[n];
for (int i = 0; i < n; ++i) {
e[i] = new ArrayList<>();
}
for (int i = 0; i < m; ++i) {
str = reader.readLine().split(" ");
int a = Integer.parseInt(str[0]) - 1;
int b = Integer.parseInt(str[1]) - 1;
e[a].add(b);
e[b].add(a);
}
queue = new LinkedList<>();
next = new int[n];
belong = new int[n];
mark = new char[n];
match = new int[n];
visit = new int[n];
for (int i = 0; i < n; i++) match[i] = -1;
}
/**
* 出力
*/
void print() {
int count = 0;
for (int i = 0; i < n; ++i) {
if (match[i] > i) { //>iマッチが2度カウントされるのを防ぐため、ビストはオーグ毎ではなく、LCA毎にリセットされなければならない。
count++;
}
}
System.out.println(count);
for (int i = 0; i < n; ++i) {
System.out.print(match[i] + 1 + " ");
}
}
/**
* マッチしていないノードからの拡幅
*/
void match() {
for (int i = 0; i < n; i++) if (match[i] == -1) aug(i);
}
/**
* sを始点とするオーグメントパスを見つける
*/
void aug(int s) {
//reset
for (int i = 0; i < n; i++) {
queue.clear();
next[i] = -1;
belong[i] = i;
mark[i] = 0;
}
//System.out.println("a new aug start with " + s);
mark[s] = 'S';
queue.offer(s);
//sがマッチしない場合
int n2 = next[n1];
int n3 = match[n2];
match[n2] = n1;
match[n1] = n2;
n1 = n3;
}
break; // オーグメンテーションが成功し、ループを抜けると次のステージに移る
} else { // 現在のサーチのクロスチェイン+y+match[y]新しいクロスチェーンの形成はmatch[y]検索されるノードとしてキューに加わる
next[y] = x;
//System.out.println(match[y] + " match of " + y + " added");
queue.offer(match[y]);
mark[match[y]] = 'S'; // match[y]また、S字型である。
mark[y] = 'T'; // yTにマークされる。
}
}
}
}
/**
* 点xとyの最も近い共通祖先を見つける
*/
int LCA(int x, int y) {
//System.out.println("LCA: " + x + " " + y);
for (int i = 0; i < n; i++) {// 各ステージでリラベリングする
visit[i] = -1;
}
while (true) {
if (x != -1) {
//System.out.println("LCA: " + x);
x = findb(x); // ポイントは対応するフラワーに対応しなければならない
//System.out.println("LCA: to root " + x);
if (visit[x] == 1)
return x;
visit[x] = 1;
if (match[x] != -1) {
x = next[match[x]];
//System.out.println("LCA: to next " + x);
} else x = -1;
}
//swap x and y
int tmp = x;
x = y;
y = tmp;
}
}
/**
*
*/
void group(int n1, int s) {
//ループの各ラウンドは、連結集合のルートとしてn3を使用する。
//最終的なn3はsになる。つまり、フラワーを縮小した後、sがそのフラワーのルートとして使用される。
//これは、sがこのツリーにおけるこの花の唯一の連結点であり、その上のノードがLCAで役割を果たすからである。
while (n1 != s) {
int n2 = match[n1], n3 = next[n2];
// _nextフラワー内のパスをマークするために配列が使用され、結合されたマッチ配列は、実際に双方向の連鎖リストを形成するために使用される。
if (findb(n3) != s) next[n3] = n2;
queue.offer(n2);
mark[n2] = 'S';
unit(n1, n2);
unit(n2, n3);
n1 = n3;
}
}
void unit(int a, int b) {
a = findb(a);
b = findb(b);
if (a != b) belong[a] = b;
}
int findb(int x) {
//また、探索処理では、BELONGを最適化し、連結集合のすべての点を連結集合のルートに直接指すようにする。
return belong[x] == x ? x : (belong[x] = findb(belong[x]));
}
}
}
