Pagini recente » Cod sursa (job #3265099) | Cod sursa (job #1223527) | Cod sursa (job #1958224) | Cod sursa (job #1687666) | Cod sursa (job #2666716)
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("dfs.in");
ofstream cout("dfs.out");
vector <int> M[100001];
int Viz[100001], X1, X2;
int NrComponenteConexe, Dimensiune, N1, N2;
void Dfs ( int x )
{
if ( Viz[x] == 0 )
{
Viz[x] = 1; ///vizitam nodul curent
Dimensiune = M[x].size(); ///aflam dimensiunea
for ( int i = 0; i < M[x].size(); i ++ ) ///parcurgem vectorul de muchii al nodului
if ( Viz[ M[x][i] ] == 0 ) ///daca am gasit o muchie care nu a fost vizitata
Dfs ( M[x][i] ); ///apelam recursiv
}
}
int main()
{
cin >> N1 >> N2;
for ( int i = 1; i <= N2; i ++ )
{
///adaugam nodurile, pe rand, in lista de muchii a celuilalt
cin >> X1 >> X2;
M[X1].push_back(X2);
M[X2].push_back(X1);
}
for ( int i = 1; i <= N1; i ++)
if ( Viz[i] == 0 ) ///daca nodul n-a fost vizitat
{
NrComponenteConexe++; ///actualizam nr de componente conexe
Dfs(i);
}
cout << NrComponenteConexe;
return 0;
}