[C++] Ponti

Pesanti piogge hanno colpito il territorio e molte strade sono state rese totalmente inagibili. Diverse città sono quindi state totalmente disconnesse rendendo falso questo motto: "ogni città è raggiungibile da ogni altra città".
E' necessario quindi trovare il numero mimino di strade necessario per poter riaffermare il motto del territorio.

Input
Il programma deve leggere da un file di nome “input.txt” nel quale, nella prima riga, sono presenti due interi: il numero di citta N e il numero di strade M.
Le successive M righe contengono una coppia di interi i e j. Ogni coppia rappresenta un percorso ancora agibile tra la citta i e la citta j (e viceversa).

Output
Il programma deve scrivere in un file “output.txt” il numero minimo di strade da construire per ricollegare tutte le città disconnesse.

Assunzioni
1 ≤ N ≤ 10.000
1 ≤ M ≤ 20.000
0 ≤ i, j < N

Esempio
input.txt     output.txt
52                   2
21
34

Con un grafo contiamo quanti settori (gruppi di città non collegati fra loro) e al loro numero sottraiamo 1.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53

#include<cstdlib> #include<iostream> #include<fstream> #include<vector> #include<cstring> //memset #define NODI 10000 using namespace std; int m,n,x,y,b=0,s; vector<int> c [NODI]; bool v [NODI]; ifstream in; ofstream out; void e(int k){ //esplora il grafo e quando si ferma aggiunge un blocco v[k]=1; s=c[k].size(); if(s > 0) for(int i = 0; i < s; i++){ int f = c[k][i]; if(v[f] == 0) e(v[f]);} else b++; } int main(){ in.open("input.txt"); out.open("output.txt"); in >> n>>m; memset(v,0,n); for (int i=0;i<m;i++){ in>>x>>y; c[x].push_back(y); c[y].push_back(x);} for (int i=0;i<n;i++) if(v[i]==0) e(i); out << (b-1); return 0;}