Pagini recente » Cod sursa (job #192415) | Cod sursa (job #62071) | Cod sursa (job #1853010) | Cod sursa (job #1326397) | Cod sursa (job #686376)
Cod sursa(job #686376)
#include <fstream>
//#include <iostream>
#include <vector>
#include <set>
using namespace std;
// N noduri, M muchii
int N, M;
// declar lista de adiacenta pt grafuri
vector<set <int> > graf;
// 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;
// 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[nod] = true;
set<int> :: iterator it;
// parcurg nodurile grafului
for(it = graf [nod].begin (); it != graf [nod].end (); ++ it) {
// daca nodul nu a fost vizitat si exista legatura de la nod la i
if(!VIZ[*it]) { // asa se verifica daca exista un element intr-o multime
// il vizitez
dfs(*it);
}
}
}
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();
}