Əcnəbi Mübadiləsi (Həll təhlili)

Mübadilə programının uğurla həyata keçirilməsi üçün $A$-dan $B$-yə köçmək istəyən hər bir tələbə üçün $B$-dən $A$-ya köçmək istəyən başqa bir tələbənin olması lazımdır. Yəni hər bir $(A,B)$ cütü ona uyğun olan tərs cütü $(B,A)$ ilə olmalıdır. Bu halda eyni cütlər bir neçə dəfə rastlaşa bilər.

Cütlərin saxlanılması üçün çoxluqdan istifadə edəcəyik. Proqramın iş fəaliyyətinin alqoritmini təsvir edək:

• hər bir giriş cütü $(A,B)$ üçün çoxlukda $(B,A)$ cütünün olub-olmamasını yoxlayırıq.

• əgər belə bir cüt tapılırsa, çoxluqdan onu silirik, bununla düzgün mübadilə cütü yaratmış oluruq;

• əgər tərs cüt yoxdursa, mövcud cütü $(A,B)$ çoxluğa əlavə edirik.

Bütün tələbələr işlənildikdən sonra iki hal ola bilər:

• çoxluq boşdur — bu o deməkdir ki, hər bir $(A,B)$ cütü üçün uyğun olan tərs cüt $(B,A)$ tapıldı və mübadilə proqramını uğurla həyata keçirmək mümkündür;

• çoxluq boş deyil — bu deməkdir ki, bəzi tələbələr uyğun partnyor tapılmamışdır və mübadilə proqramı mümkün deyil.

Bu əsasa görə cavab "YES" veya "NO" çıxarılır.

Nümunə

Birinci testdə hər bir $(A,B)$ cütü üçün uyğun tərs cüt $(B,A)$ tapılır. İkinci testdə tələbələrin istəyi yerinə yetirilə bilmir.

Alqoritmin icrası

Cütlər çoxluğu $s$ elan edək. Prosesdə yalnız $(A,B)$ cütləri saxlanılacaq ki, onlar üçün hələ uyğun olan $(B,A)$ cütü tapılmamışdır.

multiset<pair<int,int> > s;

Testlərin sayını $t$ oxuyuruq.

scanf("%d",&t);

Davamlı olaraq $t$ test işləmir.

while (t--)
{

Tələbələrin sayını $n$ oxuyuruq.

  scanf("%d", &n); 

Növbəti testi işlənmədən əvvəl çoxluğu təmizləyirik.

  s.clear();

Tələbələrin istəklərini ardıcıl işləyirik.

  for (i = 0; i < n; i++)
  {

Cütün $(a,b)$ oxuyuruq. Əks istiqamətdə köçmək istəyən tələbəni axtarırıq.

    scanf("%d %d", &a, &b);
    auto it = s.find({ b, a });

Əks cüt tapılmazsa, mövcud cüt $(a,b)$ çoxluğa $s$ əlavə edilir.

Əks cüt tapılırsa, bu cüt $s$-dən silinir, çünki bu cüt üçün mübadilə partnyoru tapılmışdır.

Beləliklə, $s$-də həmişə uyğunluğu tapılmamış olan cütlər saxlanılır.

    if (it == s.end()) s.insert({ a, b });
    else s.erase(it);
  }

Bütün tələbələr işlənildikdən sonra çoxluq boşdursa, bu deməkdir ki, hər bir cüt üçün əks cüt tapıldı və mübadilə proqramı uğurla həyata keçirilə bilər. Əks halda "NO" çıxarırıq.

  if (s.empty()) printf("YES\n");
  else printf("NO\n");
}