ყინულზე სრიალი



 

Bajtek-ი ყინულზე სრიალს სწავლობს. ის დამწყებია, ამიტომ მისთვის გადაადგილების ერთადერთი საშუალებაა თოვლის გროვიდან ჩრდილოეთის, სამხრეთის, აღმოსავლეთის ან დასავლეთის მიმართულებით ჩამოსრიალება, სანამ რომელიმე სხვა თოვლის გროვაზე არ მოხვდება. მან შეამჩნია, რომ ამ გზით შეუძლებელია ზოგიერთი გროვიდან გარკვეული გროვებში მოხვედრა (მოძრაობის ნებისმიერი კომბინაციით). მან გადაწყვიტა, რომ გააკეთოს თოვლის ახალი გროვები, რომ შეძლოს ნებისმიერი ლოკაციიდან ნებისმიერში მოხვედრა. შენი მიზანია დათვალო, ამისთვის საჭირო თოვლის გროვების მინიმალური რაოდენობა.

დაშვებულია, რომ Bajtek-ს თოვლის გროვების გაკეთება შეუძლია მხოლოდ მთელი რიცხვების კოორდინატებზე.

 

შემავალი მონაცემები:

პირველი ხაზი შეიცავს ერთ მთელ რიცხვს n (1n100) - თოვლის გროვების რაოდენობა. მას მოსდევს n რაოდენობის ხაზი, რომელთაგან თითოეული შეიცავს ორ მთელ რიცხვს xi და yi (1xi,yi1000) – i-ური თოვლის გროვის კოორდინატები.

გაითვალისწინეთ, რომ ჩრდილოეთი მიმართულება მიყვება Oy აქსისას, შესაბამისად აღმოსავლეთი მიუყვება Ox აქსისას. ყველა თოვლის გროვის ლოკაცია განსხვავებულია.

გამომავალი მონაცემები:

გამოიტანეთ შესაქმნელი თოვლის გროვების მინიმალური რაოდენობა იმისთვის, რომ Bajtek-მა შეძლოს ნებისმიერი თოვლის გროვიდან ნებისმიერში მოხვედრა.

მაგალითები:

შემავალი მონაცემები

2

2 1

1 2

გამომავალი მონაცემები

1

 

შემავალი მონაცემები

2

2 1

4 1

გამომავალი მონაცემები

0

 


 

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

დავაკვირდეთ იმ ფაქტს, რომ თუ ორ წვეროს შორის ვერანაირი გზა ვერ ვიპოვეთ, საკმარისია მხოლოდ ერთი წვეროს დამატება, რომელსაც ექნება ისეთი x და y კოორდინატი, რომ ემთხვეორეს ერთის x- და მეორის y-ს ან პირიქით. იხილეთ ნახაზი:

ნახაზი1

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

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

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

start - საწყისი წვერო
n - წვეროების რაოდენობა 
1  DFS(start, n):
2      თუ start მონახულებულია, დაბრუნდი
3      მონიშნე start როგორც მონახულებული
4      ყველა i-ური წვეროსთვის (0-დან n-მდე)  
5          თუ წიბო i არ არის მონახულებული, მაშინ
6              რეკურსიულად გამოიძახე DFS(start,i)

 

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

 

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

#include <cstdio>
#include <vector>
#include <iostream>
using namespace std;


// "pile" structure resembles pile of snow (edge in graph), x and y are coordinates.
// boolean helps us keep information about edges that we have visited.
struct pile{
    int x, y; 
    bool visited; 
    pile(int a, int b): x(a), y(b), visited(0) {};
};

// visit all the edges that are connected to "start" edge
void DFS(int start, int n, vector<pile>& graph){
    if(graph[start].visited == 1) return;
    graph[start].visited = 1;
    for(int curr = 0; curr < n; curr++)
        if(graph[curr].x == graph[start].x || graph[curr].y == graph[start].y) 
            DFS(curr, n, graph);
    return;
}
// find out how many edges we have.
// store information about coordinates of edges in a vector
void storeInfo(vector<pile>& graph, int& n){
    cin >> n;
    for(int i = 0; i < n; i++){
        int x, y;
        cin >> x >> y;
        graph.push_back(pile(x, y));
    }
}
int main(){
    int n; 
    vector<pile> graph;
    storeInfo(graph, n);
    // keep track of connected components in graph
    int components = 0;
    for(int i = 0; i < n; i++){
        if(graph[i].visited != 1){
            components++;
            DFS(i, n, graph);
        }
    }
    cout << components - 1 << endl;
    return 0;
}