Rezolvare completă PbInfo #2968 conexidad

Fie un graf neorientat cu N noduri și M muchii, care NU este conex.

Cerința

Să i se adauge grafului un număr minim de muchii, astfel încât acesta să devină conex. Fie extrai numărul de muchii nou-adăugate care sunt incidente cu nodul i, iar max_extra cea mai mare dintre valorile extra1, extra2,… , extraN. Mulțimea de muchii adăugate trebuie să respecte condiția ca valoarea max_extra să fie minimă.

Date de intrare

Pe prima linie a fișierului de intrare conexidad.in se află două numere naturale N și M, iar pe fiecare dintre următoarele M linii se află câte o pereche de numere a, b, semnificând faptul că există muchia [a,b]. Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire conexidad.out va conține pe prima linie valoarea max_extra. Pe a doua linie va conține valoarea K reprezentând numărul de muchii nou-adăugate în graf. Fiecare dintre următoarele K linii va conține câte o pereche de numere c, d, separate prin câte un spațiu, semnificând faptul că se adaugă grafului muchia [c,d].

Restricții și precizări

  • 1 ≤ N ≤ 100
  • 0 ≤ M ≤ N*(N-1)/2
  • Nodurile grafului sunt numerotate de la 1 la N inclusiv.
  • Muchiile prezente în fișierul de intrare sunt distincte.
  • Pentru orice muchie [a,b] aflată în fișierul de intrare, avem a ≠ b.
  • Graful din fișierul de intrare nu este conex.
  • În cazul în care soluția afișată pentru un anumit test conectează graful cu număr minim de muchii, dar nu minimizează valoarea lui max_extra, se vor acorda 50% din punctajul pentru testul respectiv.
  • Dacă există mai multe soluții optime, se va admite oricare dintre acestea.
  • În concurs s-au acordat 10 puncte din oficiu. Aici se acordă pentru exemplele din enunț.

Exemplul 1:

conexidad.in

4 2
1 2
4 2

conexidad.out

1
1
3 1

Explicație

Graful este format din două componente conexe, cu noduri din mulțimea {1, 2, 4} respectiv nodul izolat 3. După adăugarea muchiei (3,1) vom avea valorile extra1=1, extra2=0, extra3=1, extra4=0, deci max_extra = 1. Se poate demonstra că nu există soluție cu max_extra < 1.

Exemplul 2:

conexidad.in

5 1
3 4

conexidad.out

2
3
1 3
2 3
4 5

Explicație

Graful este format din patru componente conexe, cu noduri din mulțimea {3, 4}, respectiv nodurile izolate 1, 2 și 5. După adăugarea muchiilor (1,3), (2,3) și (4,5), vom avea valorile extra1=1, extra2=1, extra3=2, extra4=1, extra5=1, deci max_extra = 2. Se poate demonstra că nu există soluție cu max_extra < 2.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema conexidad:

#include <stdio.h>
#include <algorithm>
#include <numeric>
#include <memory>
using namespace std;

using file_pointer = unique_ptr<FILE, decltype(&fclose)>;

enum { OUTSIDE_COMPONENT, IN_COMPONENT };

int p[100], extra[100];
int N, M; 

int root(int node) {
    while (node != p[node]) node = p[node];
    return node;
}

void join(int x, int y) {
    x = root(x); y = root(y);
    if (x == y) return;
    p[x] = y;
}

void solve(file_pointer& f) {
    int node[2] = {-1, -1};
    for (int lap: {OUTSIDE_COMPONENT, IN_COMPONENT}) {
        for (int i = 0; i < N; ++i) {
            if ((root(i) == root(0)) == lap 
                    && (node[lap] == -1 || extra[node[lap]] > extra[i]))  {
                node[lap] = i;
            }
        }
    }
    
    if (node[0] == -1 || node[1] == -1) {
        fprintf(f.get(), "%d\n%d\n", *max_element(extra, extra + N), 
                                      accumulate(extra, extra + N, 0) / 2);
    } else {
        join(node[0], node[1]);
        ++extra[node[0]]; ++extra[node[1]];
        solve(f);
        fprintf(f.get(), "%d %d\n", node[0] + 1, node[1] + 1);
    }
}

int main() {
    file_pointer f(fopen("conexidad.in", "r"), &fclose);
    fscanf(f.get(), "%d%d", &N, &M);
    iota(p, p + N, 0);
    for (int _ = 0; _ < M; ++_) {
        int x, y; fscanf(f.get(), "%d%d", &x, &y); --x; --y;
        join(x, y);
    }
    
    f.reset(fopen("conexidad.out", "w"));
    solve(f);
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #2968 conexidad

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2968 conexidad de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!