Yönləndir

İnternet axtarış sistemlərinin müəyyən ünvanlarda (linklərdə) yerləşən elektron sənədlərlə işlədiyi yaxşı məlumdur. Lakin, bir sənədin ünvanı həmişə unikal olmur və bir sənədə bir neçə fərqli link vasitəsilə daxil olmaq mümkündür. Gəlin bu vəziyyətin xüsusi bir halını - link yönləndirməsini nəzərdən keçirək.

Müştəri A ünvanında bir səhifə tələb etdikdə, server yeni bir səhifənin B ünvanını təmin edən xüsusi bir kodla cavab verir və müştəri bu ünvana yönləndirilir. Bu proses yönləndirmə adlanır. B səhifəsi də müştərini yeni bir səhifəyə C yönləndirə bilər və s. Beləliklə, eyni sənəd A, B və C ünvanlarında mövcud ola bilər.

Yönləndirmə məlumatları müxtəlif mənbələrdən gələ bilər, məsələn, planlaşdırılmış tarama zamanı A linkini götürən və bütün yönləndirmə zəncirindən keçən bir veb tarayıcıdan. Digər bir mənbə Twitter API ola bilər: tvitlər həmişə qısaldılmış linklər (tinylinks) ehtiva edir və orijinal sənədlərə linklər tvitlərdəki genişləndirilmiş məlumatlardan əldə edilə bilər. Əgər bir neçə mənbəniz varsa, münaqişələr yarana bilər: tutaq ki, əvvəlcə Twitter-dən məlumat əldə etdik (A->B), sonra tarayıcı A linkini götürərək Dyə aparır. Alternativ olaraq, xidmət yüklənmiş ola bilər və əvvəlcə tarayıcı sənəd A-nı əldə etməyə çalışarkən bir səhv aldı, lakin sonradan xidmət işə düşdü və tarayıcı ikinci cəhddə hədəf sənədə çatdı. Həmçinin, sənəd köhnəlibsə, link etibarsız ola bilər.

Əgər sənəd üçün bəzi statistikaları hesablamaq istəyiriksə, məsələn, bu sənədə olan linklərin sayını, bütün istinadları bir "ümumi məxrəcə" gətirmək üçün bir yol tapmalıyıq. Ən praktik "məxrəc" yönləndirmə zəncirindəki son linkdir. U yönləndirmə zəncirində son link olaraq adlandırılır, əgər U->V yönləndirməsi ilə V linkinə aparan bir yönləndirmə yoxdursa. Yönləndirmə zəncirindəki son link sənədin həqiqi ünvanı olaraq da adlandırılacaq.

Sizə N yönləndirmə haqqında məlumat verilir, hər biri i v_i> cütüdür (1 ≤ i ≤ N), burada u_i orijinal linkdir və v_i bu yönləndirmənin apardığı linkdir. Yönləndirmə i NULL> formasında gələ bilər, yəni u_{i } linki etibarsızdır. Linklər giriş sırasına görə verilir, yəni siyahıda daha sonra baş verən yönləndirmə daha müasir məlumatları ehtiva edir.

Mövcud yönləndirmə məlumatlarını işləyib hər bir M linki üçün sənədin həqiqi ünvanını müəyyən etmək üçün bir proqram yazın.

Problemi həll edərkən aşağıdakı münaqişələr yarana bilər:

• əgər bəzi link U üçün yönləndirmə zənciri dövrə vurursa, biz bu linkin həqiqi ünvanının NULL olduğunu qəbul edirik;

• əgər bəzi link U üçün bir neçə yönləndirmə seçimi varsa, biz son yönləndirməni düzgün hesab edirik;

• əgər bəzi link U üçün yönləndirmə haqqında məlumat yoxdursa, biz bu linkin həqiqi ünvanının U olduğunu qəbul edirik.