Гүүрийг онлайнаар олох¶
Бидэнд чиглэлгүй граф өгөгдсөн. Гүүр гэдэг нь хассан үед графыг холбоост биш болгодог (эсвэл илүү нарийвчлан хэлбэл холбоост компонентын тоог ихэсгэдэг) ирмэг юм. Бидний даалгавар бол өгөгдсөн граф дахь бүх гүүрийг олох явдал.
Албан бус хэлбэрээр энэ даалгаврыг дараах байдлаар тавьж болно: бид өгөгдсөн замын зураг дээрх бүх "чухал" замыг олох ёстой, өөрөөр хэлбэл аль нэгийг нь хассан үед зарим хот бусдаас хүрэх боломжгүй болоход хүргэдэг замуудыг олно.
Энэ даалгаврыг гүнзгийрүүлэх хайлт-ын тойролтоор боддог Гүүрийг $O(N+M)$-д олох өгүүлэл аль хэдийн байгаа. Энэ алгоритм хамаагүй илүү нарийн төвөгтэй байх боловч нэг том давуу талтай: энэ өгүүлэлд тайлбарласан алгоритм онлайнаар ажилладаг бөгөөд энэ нь оролтын графыг урьдчилан мэдэх шаардлагагүй гэсэн үг юм. Ирмэгүүдийг нэг нэгээр нь нэмэх ба нэмэлт бүрийн дараа алгоритм одоогийн граф дахь бүх гүүрийг дахин тоолно. Өөрөөр хэлбэл алгоритмыг динамик, өөрчлөгдөж буй граф дээр үр ашигтай ажиллахаар зохион бүтээсэн.
Илүү нарийвчлан бодлогын томьёолол дараах байдалтай: Эхэндээ граф хоосон бөгөөд $n$ оройноос тогтоно. Дараа нь бид графт нэмэгдсэн ирмэгийг тэмдэглэх оройн хос $(a, b)$-г хүлээн авна. Хүлээн авсан ирмэг бүрийн дараа, өөрөөр хэлбэл ирмэг бүрийг нэмсний дараа граф дахь гүүрийн одоогийн тоог гарга.
Мөн бүх гүүрийн жагсаалтыг хөтлөх, түүнчлэн 2-ирмэгээр холбоост компонентуудыг шууд дэмжих боломжтой.
Доор тайлбарласан алгоритм $O(n \log n + m)$ хугацаанд ажиллана, энд $m$ нь ирмэгийн тоо юм. Алгоритм нь Огтлолцолгүй олонлогийн нэгдэл өгөгдлийн бүтэц дээр суурилна. Гэвч энэ өгүүлэл дэх хэрэгжүүлэлт $O(n \log n + m \log n)$ хугацаа авна, учир нь энэ нь зэргээр нэгтгэхгүй DSU-ийн хялбарчилсан хувилбарыг ашигладаг.
Алгоритм¶
Эхлээд $k$-ирмэгээр холбоост компонентыг тодорхойлъё: энэ нь $k$-ээс цөөн ирмэг хассан ч холбоост хэвээр үлддэг холбоост компонент юм.
Гүүрүүд графыг 2-ирмэгээр холбоост компонентуудад хуваадгийг харахад маш амархан. Хэрэв бид тэдгээр 2-ирмэгээр холбоост компонент бүрийг орой болгон шахаж, шахагдсан графт зөвхөн гүүрүүдийг ирмэг болгон үлдээвэл бид циклгүй граф буюу ой авна.
Доор тайлбарласан алгоритм энэ ойг мөн 2-ирмэгээр холбоост компонентуудын хамт шууд хөтөлнө.
Эхэндээ граф хоосон байхад тэр нь өөр хоорондоо холбогдоогүй $n$ ширхэг 2-ирмэгээр холбоост компонент агуулна гэдэг нь тодорхой.
Дараагийн ирмэг $(a, b)$-г нэмэхэд гурван нөхцөл байдал үүсч болно:
-
Орой $a$ ба $b$ хоёул ижил 2-ирмэгээр холбоост компонентод байна — тэгвэл энэ ирмэг гүүр биш бөгөөд ойн бүтцэд юу ч өөрчлөхгүй тул бид энэ ирмэгийг зүгээр л алгасаж болно.
Тиймээс энэ тохиолдолд гүүрийн тоо өөрчлөгдөхгүй.
-
Орой $a$ ба $b$ огт өөр холбоост компонентод байна, өөрөөр хэлбэл тус бүр нь өөр модны хэсэг юм. Энэ тохиолдолд ирмэг $(a, b)$ шинэ гүүр болох ба энэ хоёр мод нэг болж нэгдэнэ (мөн бүх хуучин гүүрүүд үлдэнэ).
Тиймээс энэ тохиолдолд гүүрийн тоо нэгээр нэмэгдэнэ.
-
Орой $a$ ба $b$ нэг холбоост компонентод боловч өөр өөр 2-ирмэгээр холбоост компонентод байна. Энэ тохиолдолд энэ ирмэг зарим хуучин гүүрүүдийн хамт цикл үүсгэнэ. Эдгээр бүх гүүр гүүр байхаа болих ба үүссэн циклийг шинэ 2-ирмэгээр холбоост компонент болгон шахах ёстой.
Тиймээс энэ тохиолдолд гүүрийн тоо нэг буюу түүнээс олноор багасна.
Улмаар бүхэл даалгавар 2-ирмэгээр холбоост компонентуудын ой дээрх эдгээр бүх үйлдлийн үр дүнтэй хэрэгжүүлэлт болж буурна.
Ойг хадгалах өгөгдлийн бүтэц¶
Бидэнд хэрэгтэй цорын ганц өгөгдлийн бүтэц бол Огтлолцолгүй олонлогийн нэгдэл юм.
Үнэндээ бид энэ бүтцийн хоёр хуулбар хийнэ:
нэг нь холбоост компонентуудыг хөтлөх, нөгөө нь 2-ирмэгээр холбоост компонентуудыг хөтлөх зориулалттай.
Мөн нэмж бид 2-ирмэгээр холбоост компонентуудын ой дахь модуудын бүтцийг заагчаар хадгална:
2-ирмэгээр холбоост компонент бүр мод дахь өвгийнхөө индекс par[]-г хадгална.
Одоо бид хэрэгжүүлж сурах шаардлагатай үйлдэл бүрийг дараалан задлан үзнэ:
-
Хоёр орой ижил холбоост / 2-ирмэгээр холбоост компонентод орших эсэхийг шалга. Үүнийг ердийн DSU алгоритмаар хийх ба бид зүгээр л DSU-уудын төлөөлөгчийг олж харьцуулна.
-
Ямар нэг ирмэг $(a, b)$-ийн хувьд хоёр модыг нэгтгэх. Орой $a$ ч, орой $b$ ч өөрсдийн модны үндэс биш байж болох тул энэ хоёр модыг холбох цорын ганц арга бол тэдгээрийн нэгийг дахин үндэслэх явдал юм. Жишээ нь та орой $a$-ийн модыг дахин үндэслээд, дараа нь $a$-ийн өвгийг $b$ болгож тохируулан түүнийг нөгөө модонд залгаж болно.
Гэвч дахин үндэслэх үйлдлийн үр ашгийн тухай асуулт гарч ирнэ: үндэс $r$-тэй модыг орой $v$ рүү дахин үндэслэхийн тулд $v$ ба $r$-ийн хоорондох зам дээрх бүх оройд зочилж, заагч
par[]-г эсрэг чиглэлд чиглүүлэх, мөн холбоост компонентуудыг хариуцдаг DSU дахь өвгүүдийн лавлагааг өөрчлөх шаардлагатай.Тиймээс дахин үндэслэх өртөг нь $O(h)$ бөгөөд энд $h$ нь модны өндөр юм. Та өртөг нь $O(\text{size})$ гэж хэлснээр бүр илүү муу үнэлгээ хийж болно, энд $\text{size}$ нь мод дахь оройн тоо юм. Эцсийн complexity ялгаагүй байх болно.
Одоо бид стандарт арга техник хэрэглэнэ: бид цөөн орой агуулсан модыг дахин үндэслэнэ. Тэгвэл хамгийн муу тохиолдол нь ойролцоогоор ижил хэмжээтэй хоёр мод нэгдэх үе болох нь зөн совингоор тодорхой боловч тэгвэл үр дүн нь хоёр дахин их хэмжээтэй мод болно. Энэ нь тухайн нөхцөл байдал олон удаа тохиолдохыг зөвшөөрөхгүй.
Ерөнхийдөө нийт өртгийг рекуррент хамаарлын хэлбэрээр бичиж болно:
$$ T(n) = \max_{k = 1 \ldots n-1} \left\{ T(k) + T(n - k) + O(\min(k, n - k))\right\} $$$T(n)$ нь модуудыг дахин үндэслэх ба нэгтгэх замаар $n$ оройтой мод авахад шаардагдах үйлдлийн тоо юм. $n$ хэмжээтэй модыг $k$ ба $n - k$ хэмжээтэй хоёр жижиг модыг нэгтгэн үүсгэж болно. Энэ рекуррент хамаарал $T(n) = O (n \log n)$ шийдтэй.
Тиймээс хэрэв бид үргэлж хоёр модны жижгийг нь дахин үндэслэвэл бүх дахин үндэслэх үйлдэлд зарцуулах нийт хугацаа $O(n \log n)$ байх болно.
Бид холбоост компонент бүрийн хэмжээг хөтлөх шаардлагатай болно, гэхдээ DSU өгөгдлийн бүтэц үүнийг хүндрэлгүй болгодог.
-
Шинэ ирмэг $(a, b)$ нэмснээр үүссэн циклийг хайх. $a$ ба $b$ модонд аль хэдийн холбогдсон тул бид орой $a$ ба $b$-ийн хамгийн бага нийтлэг өвөг-ийг олох хэрэгтэй. Цикл нь $b$-ээс LCA хүрэх, LCA-ээс $a$ хүрэх зам ба $a$-ээс $b$ хүрэх ирмэгээс тогтоно.
Циклийг олсны дараа бид илрүүлсэн циклийн бүх оройг нэг орой болгон шахна. Энэ нь бидэнд аль хэдийн циклийн урттай пропорциональ complexity байна гэсэн үг бөгөөд ингэснээр бид уртад пропорциональ дурын LCA алгоритм ашиглаж болох ба хурдан алгоритм ашиглах шаардлагагүй.
Модны бүтцийн тухай бүх мэдээлэл өвгийн массив
par[]-д байгаа тул цорын ганц үндэслэлтэй LCA алгоритм нь дараах юм: орой $a$ ба $b$-г зочилсон гэж тэмдэглээд, дараа нь бид тэдгээрийн өвөгpar[a]баpar[b]рүү очиж тэмдэглэнэ, дараа нь тэдгээрийн өвгүүд рүү аль хэдийн тэмдэглэгдсэн орой хүрэх хүртэл үргэлжлүүлнэ. Энэ орой бол бидний хайж буй LCA бөгөөд бид $a$ ба $b$-ээс LCA хүрэх замыг дахин туулснаар цикл дээрх оройнуудыг олж чадна.Энэ алгоритмын complexity нь хайж буй циклийн урттай пропорциональ болох нь илэрхий.
-
Модонд шинэ ирмэг $(a, b)$ нэмснээр циклийг шахах.
Бид илрүүлсэн циклийн бүх оройноос тогтох шинэ 2-ирмэгээр холбоост компонент үүсгэх хэрэгтэй (мөн илрүүлсэн цикл өөрөө зарим 2-ирмэгээр холбоост компонентоос тогтож болох боловч энэ нь юу ч өөрчлөхгүй). Түүнчлэн модны бүтэц эвдрэхгүй байхаар, мөн бүх заагч
par[]ба хоёр DSU зөв хэвээр байхаар тэдгээрийг шахах шаардлагатай.Үүнд хүрэх хамгийн хялбар арга бол циклийн бүх оройг тэдгээрийн LCA рүү шахах явдал юм. Үнэндээ LCA нь оройнуудын хамгийн дээд нь, өөрөөр хэлбэл түүний өвгийн заагч
par[]өөрчлөгдөхгүй үлдэнэ. Циклийн бусад бүх оройн хувьд өвгүүдийг шинэчлэх шаардлагагүй, учир нь эдгээр орой зүгээр л оршихоо болино. Гэвч 2-ирмэгээр холбоост компонентуудын DSU-д эдгээр бүх орой зүгээр л LCA руу заана.Бид 2-ирмэгээр холбоост компонентуудын DSU-г зэргээр нэгтгэх оновчлолгүйгээр хэрэгжүүлэх тул асуулга бүрд дунджаар $O(\log n)$ complexity авна. Асуулга бүрд дунджаар $O(1)$ complexity-д хүрэхийн тулд бид циклийн оройнуудыг зэргээр нэгтгэхийн дагуу нэгтгэж, дараа нь
par[]-г түүнд харгалзуулан оноох хэрэгтэй.
Implementation¶
Here is the final implementation of the whole algorithm.
As mentioned before, for the sake of simplicity the DSU of the 2-edge-connected components is written without Union by rank, therefore the resulting complexity will be $O(\log n)$ on average.
Also in this implementation the bridges themselves are not stored, only their count bridges.
However it will not be difficult to create a set of all bridges.
Initially you call the function init(), which initializes the two DSUs (creating a separate set for each vertex, and setting the size equal to one), and sets the ancestors par.
The main function is add_edge(a, b), which processes and adds a new edge.
vector<int> par, dsu_2ecc, dsu_cc, dsu_cc_size;
int bridges;
int lca_iteration;
vector<int> last_visit;
void init(int n) {
par.resize(n);
dsu_2ecc.resize(n);
dsu_cc.resize(n);
dsu_cc_size.resize(n);
lca_iteration = 0;
last_visit.assign(n, 0);
for (int i=0; i<n; ++i) {
dsu_2ecc[i] = i;
dsu_cc[i] = i;
dsu_cc_size[i] = 1;
par[i] = -1;
}
bridges = 0;
}
int find_2ecc(int v) {
if (v == -1)
return -1;
return dsu_2ecc[v] == v ? v : dsu_2ecc[v] = find_2ecc(dsu_2ecc[v]);
}
int find_cc(int v) {
v = find_2ecc(v);
return dsu_cc[v] == v ? v : dsu_cc[v] = find_cc(dsu_cc[v]);
}
void make_root(int v) {
int root = v;
int child = -1;
while (v != -1) {
int p = find_2ecc(par[v]);
par[v] = child;
dsu_cc[v] = root;
child = v;
v = p;
}
dsu_cc_size[root] = dsu_cc_size[child];
}
void merge_path (int a, int b) {
++lca_iteration;
vector<int> path_a, path_b;
int lca = -1;
while (lca == -1) {
if (a != -1) {
a = find_2ecc(a);
path_a.push_back(a);
if (last_visit[a] == lca_iteration){
lca = a;
break;
}
last_visit[a] = lca_iteration;
a = par[a];
}
if (b != -1) {
b = find_2ecc(b);
path_b.push_back(b);
if (last_visit[b] == lca_iteration){
lca = b;
break;
}
last_visit[b] = lca_iteration;
b = par[b];
}
}
for (int v : path_a) {
dsu_2ecc[v] = lca;
if (v == lca)
break;
--bridges;
}
for (int v : path_b) {
dsu_2ecc[v] = lca;
if (v == lca)
break;
--bridges;
}
}
void add_edge(int a, int b) {
a = find_2ecc(a);
b = find_2ecc(b);
if (a == b)
return;
int ca = find_cc(a);
int cb = find_cc(b);
if (ca != cb) {
++bridges;
if (dsu_cc_size[ca] > dsu_cc_size[cb]) {
swap(a, b);
swap(ca, cb);
}
make_root(a);
par[a] = dsu_cc[a] = b;
dsu_cc_size[cb] += dsu_cc_size[a];
} else {
merge_path(a, b);
}
}
The DSU for the 2-edge-connected components is stored in the vector dsu_2ecc, and the function returning the representative is find_2ecc(v).
This function is used many times in the rest of the code, since after the compression of several vertices into one all these vertices cease to exist, and instead only the leader has the correct ancestor par in the forest of 2-edge-connected components.
The DSU for the connected components is stored in the vector dsu_cc, and there is also an additional vector dsu_cc_size to store the component sizes.
The function find_cc(v) returns the leader of the connectivity component (which is actually the root of the tree).
The re-rooting of a tree make_root(v) works as described above:
if traverses from the vertex $v$ via the ancestors to the root vertex, each time redirecting the ancestor par in the opposite direction.
The link to the representative of the connected component dsu_cc is also updated, so that it points to the new root vertex.
After re-rooting we have to assign the new root the correct size of the connected component.
Also we have to be careful that we call find_2ecc() to get the representatives of the 2-edge-connected component, rather than some other vertex that have already been compressed.
The cycle finding and compression function merge_path(a, b) is also implemented as described above.
It searches for the LCA of $a$ and $b$ be rising these nodes in parallel, until we meet a vertex for the second time.
For efficiency purposes we choose a unique identifier for each LCA finding call, and mark the traversed vertices with it.
This works in $O(1)$, while other approaches like using $set$ perform worse.
The passed paths are stored in the vectors path_a and path_b, and we use them to walk through them a second time up to the LCA, thereby obtaining all vertices of the cycle.
All the vertices of the cycle get compressed by attaching them to the LCA, hence the average complexity is $O(\log n)$ (since we don't use Union by rank).
All the edges we pass have been bridges, so we subtract 1 for each edge in the cycle.
Finally the query function add_edge(a, b) determines the connected components in which the vertices $a$ and $b$ lie.
If they lie in different connectivity components, then a smaller tree is re-rooted and then attached to the larger tree.
Otherwise if the vertices $a$ and $b$ lie in one tree, but in different 2-edge-connected components, then the function merge_path(a, b) is called, which will detect the cycle and compress it into one 2-edge-connected component.