ჰონგქოუ აშენებს სახელმწიფოს



ჰონგქოუ მსოფლიოს მმართველია. როგორც მსოფლიოს მმართველს, მას უნდა, რომ ხალხებისთვის თავიანთი ქვეყნების შიგნით მოძრაობა გააადვილოს.            მსოფლიო შეძლება წარმოდგეს, როგორც არამიმართული გრაფი (undirected graph) n ცალი წვეროთი და m ცალი წიბოთი. K ცალი წვერო წარმოადგენს K ცალი სახელმწიფოს მთავრობის სახლებს. სახელმწიოები ერთად მსოფლიოს ქმნიან.

 

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

            ჰონგქოუს უნდა, რომ დაამატოს რაც შეიძლება მეტი წიბო წვეროებს შორის ისე, რომ გრაფი ისევ სტაბილური იყოს.    დაადგინეთ წიბოების მაქსიმალური რაოდენობა, რაც ჰონგქოუს შეუძლია დაამატოს გრაფში.

 

შესატანი მონაცემები:

            შესატანი მონაცემების პირველი ხაზი შეიცავს სამ მთელ რიცხვს n,m, და k (1<= n <= 1 000, 0<= m <= 100 000 , 1 <= k <= m ) – წვეროებისა და წიბოების რაოდენობა გრაფში და მთავრობის სახლების რაოდენობა.

            შესატანი მონაცემების მეორე ხაზი შეიცავს კ ცალ მთელ რიცხვს c1,c2 … ck (1<= ci <= n). ეს მთელი რიცხვები წყვილ-წყვილად განსხვავებულია და თითოეული წარმოადგენს მთავრობის სახლის წვეროს მსოფლიოში.

            შესატანი მონაცემების დანარჩენი m ხაზი შეიცავს ორ მთელ რიცხვს ui და vi (1<= ui ,  vi <= n). ეს ორი წვერო წარმოადგენს არამიმართულ წიბოს ui  და  vi წვეროებს შორის.

            გარანტირებულია, რომ შესატანი მონაცემებით შეყვანილი გრაფი სტაბილური იქნება.

გამოსატანი მონაცემები:

            გამოსატანი მონაცემი ერთი მთელი რიცხვია –  წვეროების მაქსიმალური რაოდენობა, რაც შეუძლია ჰონგქოუს  დაამატოს გრაფში, ისე რომ გრაფი კვლავ სტაბილური იყოს.

მაგალითები:

 

 

შესატანი მონაცემები

4 1 2

1 3

1 2

გამოსატანი მონაცემები

2

 

შესატანი მონაცემები

3 3 1

2

1 2

1 3

2 3

გამოსატანი მონაცემები

0


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

ამოხსნისთვის შეყვანილ გრაფს შევინახავთ ვექტორების მასივში, რომელშიც I-ურ ინდექსზე მყოფ ვექტორში დამახსოვრებული იქნება I-ური წვეროს მეზობელი წვეროები, შემოვიტანთ int ტიპის ცვლადს result, რომელშიც შევინახავთ ჩამატებული წვეროების რაოდენობას, ასევე შემოვიღებთ ორ set-ს (visited და governments - ერთს სიგანეში ძებნის ფუნქციისთვის უკვე გავლილი წვეროების მოსანიშნად, ხოლო მეორეს განსაკუთრებული წვეროების შესანახად)  და ორ int ტიპის ცვლადს (maxConnectedComponents და count – ყველაზე დიდი განსაკუთრებული წვეროს შემცველი კომპონენტის წვეროების რაოდენობას და ბმულ კომპონენტში წვეროების რაოდენობას).

            მონაცემთა წაკითხვის შემდეგ government სეტის თითოეული ელემენტიდან გამოვიძახოთ dfs. Dfs-ით ვიპოვით government სეტის i-ური ელემენტის შემცველ ბმულ კომპონენტში წვეროების რაოდენობას(count).   

count-ს გაგების შემდეგ i-ური კომპონენტი უნდა გავხადოთ სრული (სრული გრაფი - ყველა წვერო ყველასთანაა დაკავშირებული და თუ წვეროების რაოდენობაა N მაშინ წიბოების რაოდენობა გამოითვლება N*(N-1)/2 ფორმულით, კომპონენტების სრულად გადაქცევის შემდეგ გრაფი ისევ სტაბილური დარჩება) ანუ დავითვალოთ კომპონენტისთვის სრულად გადაქცევის შემთხვევაში რამდენი წიბო გვექნება (count*(count 1)/2) და მიღებული რიცხვი დავუმატოთ results. ასევე ვიმახსოვროთ მაქსიმალური ზომის კომპონენტის წვეროების რაოდენობა maxConnectedComponents. Dfs-ის გამოძახებისას  ვიმახსოვრებთ   გავლილ წვეროებს visited სეტში. შეყვანილი წვეროების რაოდენობა  n-ის და visited სეტის სიგრძის სხვაობით გავიგებთ იმ წვეროების რაოდენობას(freeNodes), რომლებიც არ მოხვდნენ განსაკუთრებული წვეროების შემცველ ბმულ კომპონენტებში. Result-ს გამოვაკლებთ  maxConnectedComponents (ყველაზე დიდი განსაკუთრებული წვეროს შემცველი კომპონენტის წვეროების რაოდენობა), რადგან ყველაზე დიდი ზომის კომპონენტის თავისუფალ წვეროებთან გაერთიანების შემდეგ შედეგში ორჯერ არ შევიდეს. შემდეგ თავისუფალ წვეროებს გავაერთიანებთ ყველაზე დიდ ნაპოვნ ბმულ კომპონენტთან, რის შედეგადაც მივიღებთ  maxConnectedComponents+ freeNodes წვეროებიან კომპონენტს და ამ კომპონენტსაც ვაქცევთ სრულად. ჩვენს შემთხვევაში უბრალოდ წიბოების რაოდენობას დავითვლით (maxConnectedComponent +freeNodes)*(maxConnectedComponent  + freeNodes -1) / 2 და results დავუმატებთ. ამ ყველაფრის შედეგად result-ში შენახულია გრაფში ყველა წიბოს რაოდენობა ამიტომ results უნდა გამოვაკლოთ გრაფში თავდაპირველი წიბოების რაოდეობა  M და მივიღებთ ჩამატებული წიბოების რაოდენობას. (თავისუფალი წვეროები ჩავამატეთ ყველაზე დიდი ზომის კომპონენტში, იმიტომ , რომ თუ გვაქვს სრული კომპონენტი ზომით A  და ერთი წვერო ,რომელიც უნდა ჩავამატოთ ამ კომპონენტში ისე, რომ კომპონენტი ისევ სრული იყოს, მოგვიწევს A ცალი წიბოს დამატება. ე.ი A რაც უფრო დიდია მით უფრო მეტ წიბოს ვამატებთ).

 

#include <iostream>
#include <vector>
#include <set>

using namespace std;

set<int>visited;
set<int>governments;
vector<int>neighbours[10001];
int maxConnectedComponent;
int count;

void dfs(int vertex){
    visited.insert(vertex);
    count++;
    for(int i = 0; i < neighbours[vertex].size(); i++){
        if(visited.count(neighbours[vertex][i]) == 0){
            dfs(neighbours[vertex][i]);
        }
    }
}

int main() {
	int n, m, k, g, u, v;
    maxConnectedComponent = 0;
    count = 0;
    int result = 0;
    cin >> n >> m >> k;
    for(int i = 0; i < k; i++){
        cin >> g;
        governments.insert(g);
    }
    for(int i = 0; i < m; i++){
        cin >> u >> v;
        neighbours[u].push_back(v);
        neighbours[v].push_back(u);
    }
    //find the biggest connected componenet containing government node
    set<int>::iterator it;
    for(it = governments.begin(); it != governments.end(); it++){
        count = 0;
        dfs(*it);
        result += (count*(count - 1)/2);
        if(count > maxConnectedComponent){
            maxConnectedComponent = count;
        }
    }

    int freeNodes = n - visited.size();
    result = result - (maxConnectedComponent*(maxConnectedComponent - 1)/2);
    result += (maxConnectedComponent + freeNodes)*(maxConnectedComponent + freeNodes -1)/2;
    cout << result - m;
    return 0; 
}