Pagini recente » Cod sursa (job #2277794) | Cod sursa (job #155248) | Cod sursa (job #262845) | Cod sursa (job #261449) | Cod sursa (job #2797895)
#include <iostream>
#include <fstream>
#include <vector>
#define MAX 100001
using namespace std;
ifstream fin ("dfs.in");
ofstream fout("dfs.out");
class Graf{
public:
//date membre
vector <int> A[MAX]; //liste de adiacenta
int mM, mN;
int nrComp; //nr comp conexe
static bool viz[MAX];
//constructor
Graf(int N, int M){
mN = N;
mM = M;
nrComp = 0;
}
void CitireG(){
int x, y;
for(int i = 1; i <= mM; i++){
// citim muchiile
fin >> x >> y;
A[x].push_back(y); //adaugam ambele noduri in lista celuilalt de adiacenta
A[y].push_back(x); //deoarece graful e neorientat
}
}
void DFS(int start);
void ComponenteConexe();
};
bool Graf :: viz[MAX] ={0};
void Graf :: DFS (int start){
viz[start] = 1;
// vizitam nodul din care plecam
for(int i = 0; i < A[start].size(); i++){
// parcurgem toti vecinii nodului start
if(!viz[A[start][i]] ){
// daca nu am mai vizitat acest vecin
DFS(A[start][i]);
}
}
}
void Graf :: ComponenteConexe(){
for(int i = 1; i <= mN; i++){
if(!viz[i]){
nrComp++;
DFS(i);
}
}
}
int main(){
int N, M;
fin >> N >> M;
Graf G(N,M);
G.CitireG();
G.ComponenteConexe();
fout<<G.nrComp;
return 0;
}