F. Хуваагдах чанар бүхий граф дахь бүлэглэл

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Чиглэлгүй графын хувьд бүлэглэл гэж аль ч хоёр орой нь хоорондоо ирмэгээр холбогдсон байх дэд графыг хэлнэ. (Оройнуудын хоосон олонлог болон зөвхөн нэг оройноос бүтсэн олонлогууд аль аль нь бүлэглэл болж чадна).

Мэдэж байгаачлан дурын граф дахь хамгийн их боломжит бүлэглэлийн (clique) тухай асуудал нь "HP-hard" төрөлд багтах нэн өндөр зэрэглэлийн асуудал. Гэхдээ одоо онцгой төрлийн зарим графын хувьд үүнийг шийдье.

$A = \{a_{1}, a_{2}, ..., a_{n}\}$ гэсэн эерэг бүхэл тоонуудын олонлогийн хувьд хуваагдах чанар бүхий графыг тодорхойльё. Өөрөөр хэлбэл $A$ олонлогийн элементүүдээр оройнууд тодорхойлогдох ба $a_{i}$ ба $a_{j}$ ($i ≠ j$) тоонуудын аль нэг нь нөгөөгөө хувааж байвал уг хоёр тоогоор илэрхийлэгдэх хоёр оройг ирмэгээр холбоно.

Хэрэв сөрөг биш бүхэл тоонуудын $A$ олонлог өгөгдсөн бол уг олонлогийн хувьд хамгийн олон оройтой бүлэглэлийг олж оройн тоог хэвлэнэ үү.

Оролт

Эхний мөрөнд $A$ олонлогийн чадлыг тодорхойлох $n$ ($1 ≤ n ≤ 10^{6}$) бүхэл тоог оруул.

Хоёр дахь мөрөнд $A$ олонлогийн элементүүд болох $a_{1}, a_{2}, ..., a_{n}$ ($1 ≤ a_{i} ≤ 10^{6}$) гэсэн $n$ ялгаатай эерэг бүхэл тоонуудыг оруул.

Гаралт

$A$ олонлогийн хувьд үүсэх хамгийн том бүлэглэлийн оройн тоог хэвлэнэ үү.

Орчуулсан: Э.Оргил-Эрдэнэ

Жишээ тэстүүд

Оролт
8
3 4 6 8 10 18 21 24
Гаралт
3

Тэмдэглэл

Жишээнд $\{3, 6, 18\}$ тоонуудаас бүрдсэн $3$ элементтэй бүлэглэл олдож байна. Энэ графт үүнээс олон оройтой бүлэглэл байхгүй.

Сэтгэгдлүүдийг ачааллаж байна...