Pagini recente » Cod sursa (job #2384760) | Cod sursa (job #1918991) | Cod sursa (job #910712) | Cod sursa (job #2882273) | Cod sursa (job #686330)
Cod sursa(job #686330)
#include <fstream>
//#include <iostream>
#include <vector>
#include <set>
using namespace std;
// N noduri, M muchii
int N, M;
// declar matricea
vector<int> graf[100001];
// multime de noduri nevizitate - daca exista e vizitat
bool VIZ[100001];
// functii interne
void citire();
void dfs();
void rez();
int main() {
citire();
rez();
}
void citire() {
ifstream fin("dfs.in");
fin>>N>>M;
// citesc muchiile
int a, b;
for(int i=1; i<=M; i++) {
// citesc valorile
fin>>a>>b;
// adaug nodului a, nodul b in lista de adiacenta
graf[a].push_back(b);
// graful este neorientat
graf[b].push_back(a);
}
fin.close();
}
void dfs(int nod) {
// marchez nodul curent ca vizitat
VIZ[nod] = true;
// parcurg vecinii nodului nod
for(int i = 0; i < graf[nod].size(); i++) {
// daca nodul nu a fost
if(!VIZ[graf[nod][i]]) {
// il vizitez
dfs(graf[nod][i]);
}
}
}
void rez() {
// ca sa verific cate componente conexe are un graf
// il parcurg prin DFS pornind din fiecare nod
// si daca la fiecare parcurgere gasesc un nod nevizitat,
// atunci am gasit o comp conexa
int compConexe = 0;
for(int i=1; i<=N; i++) {
if(!VIZ[i]) {
compConexe++;
dfs(i);
}
}
// afisez rezultatul
ofstream fout("dfs.out");
fout<<compConexe;
fout.close();
}