# PBinfo #2968 – conexidad – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

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.

## Cod sursă C++

```cpp
#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;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/2968)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/2968/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-2968/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)