Pagini recente » Cod sursa (job #901324) | Cod sursa (job #2056492) | Cod sursa (job #750942) | Cod sursa (job #1010385) | Cod sursa (job #2001953)
#include <iostream>
#include <fstream>
#define NMAX 100001
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
struct nod{
int val;
nod * urm;
}* v[NMAX];
int n, m;//date intrare
int componenta[NMAX];
int nrComp;
void initalizare(){
for(int i = 1; i <= n; i++){
v[i] = NULL;
componenta[i] = 0;
}
}
void citire(){
in >> n >> m;
initalizare();
for(int i = 1; i <= m; i++){
int x, y;
in >> x >> y;
nod * deAd1 = new nod;
deAd1 -> val = y;
deAd1 -> urm = v[x];
v[x] = deAd1;
nod * deAd2 = new nod;
deAd2 -> val = x;
deAd2 -> urm = v[y];
v[y] = deAd2;
}
}
void DFS(int plec, int index){
int stiva[NMAX], vf;
stiva[1] = plec;
vf = 1;
componenta[plec] = index;
while(vf != 0){
nod * parcurg = new nod;
parcurg = v[stiva[vf]];
bool ok = false;//ver daca vf are vecini nevizitati
while (parcurg != NULL) {
if(componenta[parcurg -> val] == 0){
ok = true;
componenta[parcurg -> val] = index;
stiva[++vf] = parcurg -> val;
parcurg = NULL;
}
else parcurg = parcurg -> urm;
}
if(ok == false)
vf --;
}
}
void rezolvare(){
for(int i = 1; i <= n; i++)
if(componenta[i] == 0){
nrComp++;
DFS(i, nrComp);
}
}
void afisare(){
out << nrComp;
}
int main(){
citire();
rezolvare();
afisare();
return 0;
}