e-olymp
Məsələlər

Maksimal dəst

Maksimal dəst

Ömür boyu gözlədiyiniz gün gəlib çatdı: Siz maksimal dəst məsələsini həll etmək üçün üsul kəşf etdiniz: istiqamətlənməmiş qraf verilir, dəst formalaşdıran qrafın təpə nöqtələrinin maksimal altçoxluğunu tapmaq lazımdır (bütün təpə nöqtələri cüt-cüt birləşdirilmişdir. Bu məsələ NP-çətinliklidir, lakin sizin əlinizdə isbat vardır ki, P = NP!

Təəssüf ki, elmi cəmiyyət Sizi heç eşitmək də istəmir. Sizin bu məsələ ilə bağlı sənədləriniz hazırki vaxtda qəbul edilməmişdir, ona görə ki, “həlli olmayan məsələnin həlli yoxdur”. Sizin telefon nömrəniz artıq tanıdığınız bütün kompüter elmləri professorlаrının ləğv etmə siyahsındadır. Dünya, belə çıxır ki, sizi görmək istəmir.

Onda siz maksimal dəstin tapılması məsələsinin həlli alqoritmini tərtib etmək və onu İnternetdə yerləşdirmək qərarına gəldiniz ki, hər bir kəs Sizin doğru olduğunuzu sərbəst yoxlaya bilsin. Siz artıq testləşdirici sistemi reallaşdırmısınız və bunun üçün demək olar ki, veb-saytı yükləmişiniz, lakin sonra Siz başa düşdünüz ki, bu elə də yaxşı ideya deyil. Əgər Siz həlledicinin əlyetərli olmasını təmin edərsinizsə, onda hər kəs NP-məsələlərini maksimal dəstin tapılmasına gətirərək həll edə bilər. Əgər insanlar Sizə məşhurluq və hörmət gətirilməsi üçün sadəcə Sizin kəşfinizi sakitcə istifadə edərlərsə, nə etməli?

Xoşbəxtlikdən Sizin bildiyiniz maksimal dəst haqqında məsələnin NP-mürəkkəbliyinin yeganə isbatı onun kifayət qədər spesifik üsulla 3-SAT məsələsinə çevirməkdən ibarətdir. Buna görə Siz yoxlamaq qərarına gəldiniz ki, o çevirmə nəticəsində Sizin həlləedici üçün giriş qrafı alındımı və əgər alındısa, onda Siz məsələnin həllindən imtina edəcəksiniz. Bu şəkildə heç kəs NP sinifli məsələlər üçün cəld həll tapa bilməyəcək, lakin hər bir kəs Sizin həlledicinizin girişinə başqa formada qraf verərək onun işini yoxlaya bilər.

3-SAT məsələsi növbəti şəkildə ifadə olunur: prb3411-1,

şəklində düstur verilir, burada hər bir tij terimi bul dəyişkəni və ya unun inkarıdır (daha formal olaraq ya xk, ya da ¬xk). Düsturun doğru olması üçün dəyişkənlərə qiymət verilməsinin mümkünlüyünü təyin etmək lazımdır. Mötərizədəki hər üç term müxtəlif dəyişkənləri təmsil etməlidir.

Cevirmə növbəti şəkildə işləyir. Cari düstura görə hər biri bir mötərizə dəyişkəninə uyğun gələn 3n təpə nöqtəli qraf quraq. tijtrs termlərinə uyğun gələn iki təpə nöqtəsi ir (termlər müxtəlif mötərizə ifadələrinə məxsusdur) olarsa, tillərlə birləşdirilir və termlər ziddiyətli deyildirlər (onlar ya eynidirlər, ya da müxtəlif dəyişkənləri təmsil edirlər).

Növbəti şəkildə (x1x2¬x3)(¬x1¬x2x4)(¬x1¬x2¬x4) düsturu ilə alınan qraf təsvir olunmuşdur:

prb3411

n-ölçülü dəst dəyişkən qiymətə doğru/yanlış qiymətinin elə mənimsədilməsinə uyğundur ki, hər bir mötərizə ifadəsində heç olmazsa bir dəyişkən doğru qiymətini alır. Şəkildə 3 ölçüsündə dəst təşkil edən tillər seçilmişdir. x1–in yanlış və x2–nin doğru qurulması x3x4 dəyişkənlərinin qiymətlərindən asılı olmayaraq bütün mötərizə ifadələrinin yerinə yetirilməsini təmin edir.

Verilmiş qrafa görə onun yuxarıda şərh edilən çevirməyə görə alınmasını mümkünlüyünü təyin etmək lazımdır. Təpə nöqtələri ixtiyari ardıcıllıqda verilə bilər.

Giriş verilənləri

Giriş faylının birinci sətrində qrafın təpə nöqtələrinin və tillərinin sayını ifadə edən iki v (1v100) və e tam ədədləri verilir. Hər bir növbəti e sətrdə tillə birləşdirilmiş təpə nöqtələrinin sayını ifadə edən iki tam ədəd verilir. Hər bir təpə nöqtəsi cütlüyü birdən çox olmayaraq birləşdirilib, heç bir til təpə nöqtəsini özü ilə birləşdirmir.

Çıxış verilənləri

Göstərilən çevirmə nəticəsində verilmiş qrafı əldə etmək mümükün olarsa, "YES" və əks halda "NO" verməli.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB
Giriş verilənləri
9 22
1 3
1 6
7 1
8 9
9 1
2 3
2 4
2 5
2 6
2 8
3 4
3 5
3 7
4 8
4 9
5 6
5 7
5 8
5 9
6 7
6 9
7 8
Çıxış verilənləri
YES