Pagini recente » Cod sursa (job #1668845) | Cod sursa (job #1245569) | Cod sursa (job #1443587) | Cod sursa (job #543619) | Cod sursa (job #2928596)
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <queue>
using namespace std;
vector<set<int>> graf;
vector<int> vc;
int N, M;
void citireGraf(){
ifstream fin;
fin.open("dfs.in");
fin >> N >> M;
graf = vector<set<int>>(N+1);
vc = vector<int>(N+1);
int nod_1, nod_2;
for(int i = 1; i <= M; i++){
fin >> nod_1 >> nod_2;
graf[nod_1].insert(nod_2);
graf[nod_2].insert(nod_1);
}
fin.close();
}
void DFS(int nod_start){
//cout << nod_start << ' ';
for(int nod_vecin: graf[nod_start]){
if(!vc[nod_vecin]) {
vc[nod_vecin] = 1;
DFS(nod_vecin);
}
}
}
int Componente_Graf(){
int c = 0;
for(int i = 1; i <= N; i++){
if(!vc[i]){
c++;
DFS(i);
}
}
return c;
}
int main() {
ofstream fout("dfs.out");
citireGraf();
fout << Componente_Graf();
fout.close();
return 0;
}