Codeforces Round #804 (Div. 2)
4 өдрийн дараа |
D. Бөмбөлгөн эрэмбэлэлтийн граф
хугацааны хязгаарлалт 1 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Иахуб саяхан $n$ ширхэг $a_{1}$, $a_{2}$, ..., $a_{n}$ элементтэй сэлгэмэлийг өсөх дарааллаар эрэмбэлэдэг алгоритм болох бөмбөлгөн эрэмбэлэлтийг сурсан. Тэр энэ алгоритм маш хялбар учраас уйдсан ба тэр өөрийн гэсэн граф зохиосон. Граф анх (графыг $G$ гэе) $n$ оройтой 0 ирмэгтэй байсан. Бөмбөлгөн эрэмбэлэлтийн үеэр ирмэгүүд дараах алгоритмд тодорхойлогдсоноор гарч ирнэ (псеудокод).
procedure bubbleSortGraph()
build a graph G with n vertices and 0 edges
repeat
swapped = false
for i = 1 to n - 1 inclusive do:
if a[i] > a[i + 1] then
add an undirected edge in G between a[i] and a[i + 1]
swap( a[i], a[i + 1] )
swapped = true
end if
end for
until not swapped
/* repeat the algorithm as long as swapped value is true. */
end procedure
Графын хувьд бие даасан бүрдэл гэдэг нь ямар ч хоёр нь хөрш биш графын оройнуудын бүрдэл байна (мөн бие даасан бүрдлийн оройнуудын хооронд ямар ч ирмэг байхгүй). Хамгийн их бие даасан бүрдэл нь хамгийн олон элементтэй бүрдэл байна. Өгөгдсөн сэлгэмэлийн хувьд хэрвээ бид энэ сэлгэмэлийг bubbleSortGraph процедурын $a$ сэлгэмэлээр ашигласан бол $G$ графын хамгийн их бие даасан бүрдлийн хэмжээг ол.
Оролт
Оролтын эхний мөрөнд бүхэл тоон утга $n$ ($2 ≤ n ≤ 10^{5}$) байна. Дараагийн мөрөнд $n$ ширхэг ялгаатай бүхэл тоон утга $a_{1}$, $a_{2}$, ..., $a_{n}$ $(1 ≤ a_{i} ≤ n)$ байна.
Гаралт
Бодлогын хариу болох нэг ширхэг бүхэл тоон утгыг хэвлэ.
Орчуулсан: Г.Мэндбаяр
Жишээ тэстүүд
Оролт
3 3 1 2
Гаралт
2
Тэмдэглэл
Эхний жишээг авч үзье. Бөмбөлгөн эрэмбэлэлт 3 ба 1 элементүүдийг солино. Бид (1, 3) ирмэгийг нэмнэ. Сэлгэмэл одоо [1, 3, 2] байна. Тэгээд бөмбөлгөн эрэмбэлэлт 3 ба 2 элементүүдийг солино. Сэлгэмэл одоо [1, 3, 2] байна. Бид (2, 3) ирмэгийг нэмнэ. Сэлгэмэл одоо эрэмбэлэгдсэн байна. Бидэнд 3 орой болон (1, 3) ба (2, 3) гэсэн 2 ирмэгтэй граф байна. Үүний хамгийн их бие даасан бүрдэл нь [1, 2] байна.