კ’თულუ



 

იყო და არა იყო რა, ერთხელ ერთი კაცი მივიდა ზღვის სანაპიროსთან. ზღვა აღელვებული და ბნელი ჩანდა. კაცმა დაიწყო ძახილი, რათა პატარა ქალთევზა გამოცხადებულიყო მასთან, მაგრამ ამის მაგივრად მან გააღვიძა უძველესი ღმერთი კ’თულუ.

პარალელურად, სამყაროს მეორე ბოლოში პენტაგონი აქტიურად კრებს ინფორმაციას, რათა წინასწარ განსაზღვროს ამ მონსტრის მომდევნო მოქმედებები და ემზადება საიდუმლო იარაღის გამოყენებისთვის. დიდი სეისმური აქტივობებისა და ცუდი ამინდის გამო, სატელიტები ჯერ ვერ იძლევიან მონსტრის ნათელ სურათს. საიდუმლო იარაღიდან პირველი ნასროლის შემდეგ სატელიტის მიერ გადაღებული სურათის ანალიზი იძლევა n წვეროებითა და m წიბოებით შედგენილ არამიმართულ გრაფს. ახლა კი მსოფლიოს ყველა მხრიდან შეკრებილი გენიოსები ცდილობენ, დაადგინონ, ეს გრაფი კ’თულუს წარმოადგენს თუ არა.

ამოცანის გასაადვილებლად ჩავთვალოთ, რომ კოსმოსიდან კ’თულუ ჩანს, როგორც სფერული ტანი, რომელსაც საცებები აქვს. ფორმალურად, ჩვენ კ’თულუდ ვთვლით არამიმართულ გრაფს, რომელიც შეგვიძლია გამოვსახოთ, როგორც 3 ან მეტი ფესვიანი ხე(rooted trees), რომელთა ფესვები(roots) ერთმანეთს უკავშირდებიან მარტივი ციკლით(simple cycle).

გარანტირებულია, რომ გრაფი არ შეიცავს თვით-ციკლსა(self-loop) და ყოველ ორ წვეროს შორის გვაქვს მაქსიმუმ 1 წიბო.

თქვენი მიზანია, გაარკვიოთ ანალიზიდან მიღებული გრაფი არის თუ არა კ’თულუ.

 

Input:

პირველი ხაზი შეიცავს ორ რიცხვს – გრაფში წვეროების რაოდენობა n და წიბოების რაოდენობა m. (1 ≤ n ≤ 100, 0 ≤ m ≤ (n(n-1))/2 )

შემდეგი m რაოდენობის ხაზიდან ყოველი შეიცავს რიცხვების წყვილს x-ს და y-ს, რომლებიც აჩვენებენ, რომ არსებობს წიბო x და y წვეროებს შორის (1 ≤ x, y ≤ n, x ≠ y). ყოველ 2 წვეროს შორის არსებობს მაქსიმუმ ერთი წიბო და არცერთი წიბო არ უკავშირებს წვეროს თავის თავს.

Output:

დაბეჭდეთ "NO"(ბრჭყალების გარეშე) თუ გრაფი არ წარმოადგენს კ’თულუს, თუ იგი კ’თულუა - "FHTAGN!" .


 

მოცემულობიდან გამომდინარე შეიძლება დავასკვნათ, რომ საჭიროა: (აუცილებელი პირობა 1)გრაფი შეიცავდეს მხოლო ერთ ბმულ კომპონენტს, ანუ ყველა წვეროდან ყველა დანარჩენამდე გზა უნდა გვქონდეს, რადგან კ’თულუ ვერ იქნება ორ ნაწილად გაყოფილი. აქედან გამომდინარე გვჭირდება მინიმუმ (წვეროების რაოდენობა – 1) წიბო, რათა ყველა წვერო დავაკავშიროთ(დამფარავი ხე).

(აუცილებელი პირობა 2)რაც შეეხება 3 ან მეტ წიბოიან მარტივ ციკლს(კ’თულუს ტანი), ამის მიღება შეგვიძლია ზემოთ ხსენებულ დამფარავ ხეში კიდევ ერთი წიბოს ნებისმიერ (დაუკავშირებელ) ორ წვეროს შორის ჩასმით. ამიტომ, პირველი პირობის გათვალისწინებით, აუცილებელი პირობაა, წვეროების რაოდენობა იყოს წიბოების რაოდენობის ტოლი.

(აუცილებელი პირობა 3)ამასთან, საჭიროა შევამოწმოთ ისიც, რომ ყველა წვერო დაკავშირებული იყოს (რომელიმე წვერო არ იყოს სულ ცალკე, სხვასთან დაუკავშირებელი).

საბოლოო ჯამში ჩვენ უნდა შევამოწმოთ, რომ გრაფი შეიცავდეს მხოლოდ ერთ ბმულ კომპონენტს(1), წვეროების რაოდენობა იყოს წიბოების რაოდენობის ტოლი(2) და ყველა წვერო იყოს ყველა დანარჩენთან რაღაც გზით დაკავშირებული(3).

პირობა 1 და 3 შეიძლება ერთი ტესტით შევამოწმოთ, გააჩნია DFS როგორ დაიწერება და შესაბამისად შემოწმება როგორ დაიწერება.

რაც შეეხება პრაქტიკულ ამოხსნას, ჯერ შევამოწმებთ წიბოებისა და წვეროების რაოდენობის ტოლობას(შესრულდა პირობა 2). თუ არაა ტოლი, შეგვიძლია დავაბრუნოთ უარყოფითი პასუხი. შემდეგ ჩვენ გვჭირდება DFS-ის გამოყენება. უნდა შევქმნათ სეტი, სადაც შევინახავთ ყველა გავლილ წვეროს. თუკი ყველა წვერო დაკავშირებულია, საკმარისი იქნება ერთი DFS-ის გაშვება(ყველა წვეროს მოივლის). DFS-ის გაშვების მერე შეგვიძლია უბრალოდ შევამოწმოთ სეტი. თუკი სეტის ზომა შემოსული წვეროების რაოდენობის ტოლია, ეს იმას ნიშნავს, რომ DFS-მა გაიარა ყველა წვერო(შესრულდა პირობა 1 და 3-იც). ამოცანის სირთულე O(N)-ია, სადაც N წვეროების რაოდენობაა.

 

მაგალითი 1:

6 6		შესრულდა პირობა 2 (6 = 6). გავუშვათ DFS რომელიმე
6 3		წვეროდან. 1 → 4 → 5 → 2  სეტის ზომა  size = 4.
6 4				1 → 4 → 5           size = 4
5 1				1 → 4 		     size = 4
2 5				1 → 4 → 6 → 3   size = 6
1 4		size = შემოსული წვეროების რაოდენობა
5 4		შესრულდა 1 და 3 პირობა.  ვბეჭდავთ FHTAGN!

 

მაგალითი 2:

6 5		6 != 5, არაა კ’თულუ. ვბეჭდავთ NO	
5 6
4 6
3 1
5 1
1 2

 

ამოხსნის კოდი:

#include <iostream>
#include <set>
#include <map>
using namespace std;

void findCthulhuDFS(set<int> &been, int curVert, map<int, set<int> > &edges){
    if(been.count(curVert) != 0){
        return;
    }
    been.insert(curVert);
    set<int> curNeighbours = edges[curVert];
    for(set<int>::iterator it = curNeighbours.begin(); it != curNeighbours.end(); ++it){
        findCthulhuDFS(been, *it, edges);
    }
    return;
}


int main(int argc, char **argv){
    ios::sync_with_stdio(0);
    set<int> been;
    map<int, set<int> > edges;
    int numVertex, numEdge;
    cin >> numVertex >> numEdge;

    if(numVertex != numEdge){
        cout << "NO" << endl; 
        return 0;
    }
    int curStart, curEnd;
    for(int i = 0; i < numEdge; i++){
        cin >> curStart >> curEnd;
        edges[curStart].insert(curEnd);
        edges[curEnd].insert(curStart);
    }

    findCthulhuDFS(been, edges.begin()->first, edges);
       
    if(been.size() == numVertex){
        cout << "FHTAGN!" << endl;
    } else cout << "NO" << endl; 
    return 0;
}