Pagini recente » Cod sursa (job #390665) | Cod sursa (job #2519741) | Cod sursa (job #2512174) | Cod sursa (job #2141927) | Cod sursa (job #2636935)
#include <iostream>
#include <fstream>
#include <vector>
#define Nmax 100005
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int nr_varfuri, nr_muchii;
int componente_conexe;
vector < int > Numere[Nmax];
bool Vizitat[Nmax];
void DFS(int Nod)
{
Vizitat[Nod] = true;
for(unsigned int i = 0; i < Numere[Nod].size(); i ++)
{
int Vecin = Numere[Nod][i];
if(!Vizitat[Vecin])
DFS(Vecin);
}
}
int Read()
{
fin >> nr_varfuri >> nr_muchii;
for(int i = 1; i <= nr_muchii; i ++)
{
int x, y;
fin >> x >> y;
//stocam componentele conexe dus - intors pentru ca avem graf neorientat
Numere[x].push_back(y);
Numere[y].push_back(x);
}
/*
* 1: 2 4
* 2: 1
* 3: 5
* 4: 1
* 5: 3
* 6: -
*/
for(int i = 1; i <= nr_varfuri; i ++)
{
if(!Vizitat[i])
{
componente_conexe ++;
DFS(i);
}
}
fout << componente_conexe;
}
int main()
{
Read();
return 0;
}