Riconnessione dei PC

Corso Online per Potenziare le Competenze Digitali

Pierino ne ha combinata un’altra delle sue.
Nel laboratorio di informatica della sua scuola ha tagliato alcuni dei fili che collegavano i PC tra loro, e adesso il povero tecnico deve trovare una soluzione al più presto: il giorno delle selezioni territoriali delle OII si avvicina!
Aiuta il tecnico a capire qual è il minimo numero di fili che deve ricomprare affinché tutti i computer siano raggiungibili tra di loro (due computer A e B sono raggiungibili se è possibile andare da A a B passando su collegamenti di rete, eventualmente anche attraversando altri computer intermedi).

Dati di input

Il file input.txt è composto da M+1 righe.

• La prima riga contiene due interi separati da spazio N e M che sono, rispettivamente, il numero di PC nel laboratorio ed il numero di fili funzionanti che sono rimasti.
• Le righe dalla 2 fino alla (M+1)-esima contengono due interi A, B ciascuna: i due PC connessi dall’i-esimo dei fili rimasti (i collegamenti sono bidirezionali).

Dati di output

Il file output.txt è composto da un’unica riga contenente un unico intero, il minimo numero di fili che il tecnico deve acquistare.

Assunzioni

• 1 ≤ N ≤ 10000.
• 1 ≤ M ≤ 100000.

Esempi di input/output

input.txt	output.txt
4 2 2 1 3 0	1
6 3 1 0 5 1 0 3	2

/*
 www.valcon.it
 Corso Online per Potenziare le Competenze Digitali
 Riconnessione dei PC
*/
#include
#include	
#include
using namespace std;
	
#define NMAX 10000

vector connessioni[NMAX];
bool        connessi[NMAX];
int         visitati;

void visita(int pc)
{
	if(connessi[pc] == 0)
	{	
		visitati++;	
		connessi[pc]=true;
		for(int i=0; i < connessioni[pc].size(); i++)
			visita(connessioni[pc][i]);
	}	
}

int main()
{
	ifstream fin ( "input.txt");
    ofstream fout("output.txt");

	int N,       // n. computer 
	    M,       // n. connessioni
	    A, B;	   
	fin >> N >> M;
	for(int i=1; i <= M; i++)
	{
		fin >> A >> B;					
		connessioni[A].push_back(B);
		connessioni[B].push_back(A);
	}	
	
	int aggiunti=0;
	do
	{
		for(int i=0; i < N; i++)
			connessi[i]=false;
		visitati=0;
		visita(0);		
		if(visitati < N)
		{
			int pc=0;
			while(connessi[pc]) 
			    pc++;
			connessioni[0 ].push_back(pc);
			connessioni[pc].push_back(0 );
			aggiunti++;
		}			
	}
	while(visitati < N);
	
	fout << aggiunti;
	return 0;
}