Pagini recente » Cod sursa (job #2215821) | Cod sursa (job #1925694) | Cod sursa (job #3041815) | Cod sursa (job #2872024) | Cod sursa (job #686281)
Cod sursa(job #686281)
#include <fstream>
#include <iostream>
#include <vector>
#include <set>
using namespace std;
// N noduri, M muchii
int N, M;
// declar lista de adiacenta pt grafuri
set<int> liste;
vector<set<int> > graf(100001, liste);
// multime de noduri nevizitate - daca exista e vizitat
set<int> VIZ;
// functii interne
void citire();
void dfs();
void rez();
int main() {
citire();
rez();
}
void citire() {
ifstream fin("dfs.in");
fin>>N>>M;
// micsorez numarul de componente ale grafului
graf.resize(N+1);
// 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].insert(b);
// graful este neorientat
graf[b].insert(a);
}
fin.close();
}
void dfs(int nod) {
// marchez nodul curent ca vizitat
VIZ.insert(nod);
// parcurg nodurile grafului
for(int i=1; i<=N; i++) {
// daca nodul nu a fost vizitat si exista legatura de la nod la i
if(VIZ.find(i) == VIZ.end() && graf[nod].find(i) != graf[nod].end()) { // asa se verifica daca exista un element intr-o multime
// il vizitez
dfs(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.find(i) == VIZ.end())
compConexe++;
dfs(i);
}
// colesc memoria
VIZ.clear();
// afisez rezultatul
ofstream fout("dfs.out");
fout<<compConexe;
fout.close();
}