Pagini recente » Cod sursa (job #609097) | Cod sursa (job #692649) | Cod sursa (job #2143147) | Cod sursa (job #2790941) | Cod sursa (job #2797913)
#include <iostream>
#include <list>
#include <fstream>
#include <stack>
using namespace std;
// ifstream fin("input.txt");
// ofstream fout("output.txt");
ifstream fin("dfs.in");
ofstream fout("dfs.out");
class graf {
private:
int n;
bool este_orientat;
list<int> *ad;
public:
graf(int n=1, bool o=1) {
this->n = n;
this->este_orientat = o;
this->ad = new list<int>[n];
};
void adaug_muchie(int v, int w) {
if (este_orientat == 1)
this->ad[v].push_back(w);
else {
this->ad[v].push_back(w);
this->ad[w].push_back(v);
}
};
void BFS(int s);
void distante(int s);
void DFS(int s);
void DFS_recursiv(int s, bool *vizitat);
int nr_conexe();
};
void graf::BFS(int s) {
bool *vizitat = new bool[n];
for (int i = 0; i < n; i++) {
vizitat[i] = false;
}
list<int> coada;
vizitat[s] = true;
coada.push_back(s);
while(!coada.empty()) {
list<int>::iterator i;
s = coada.front();
fout << s << " ";
// fout << s+1 << " ";
coada.pop_front();
for (i = ad[s].begin(); i != ad[s].end(); i++) {
if (vizitat[*i] == false) {
vizitat[*i] = true;
coada.push_back(*i);
}
}
}
delete[] vizitat;
}
void graf::distante(int s) {
bool *vizitat = new bool[n];
int *distante = new int[n];
for (int i = 0; i < n; i++) {
vizitat[i] = false;
distante[i] = -1;
}
list<int> coada;
vizitat[s] = true;
coada.push_back(s);
distante[s] = 0;
while(!coada.empty()) {
list<int>::iterator i;
s = coada.front();
coada.pop_front();
for (i = ad[s].begin(); i != ad[s].end(); i++) {
if (vizitat[*i] == false) {
vizitat[*i] = true;
distante[*i] = distante[s] + 1;
coada.push_back(*i);
}
}
}
for (int i = 0; i < n; i++) {
fout << distante[i] << " ";
}
delete[] vizitat;
delete[] distante;
}
void graf::DFS(int s) {
bool *vizitat = new bool[n];
for (int i = 0; i < n; i++) {
vizitat[i] = false;
}
DFS_recursiv(s, vizitat);
delete[] vizitat;
}
void graf::DFS_recursiv(int s, bool *vizitat) {
vizitat[s] = true;
// fout << s << " ";
list<int>::iterator it;
for (it = ad[s].begin(); it != ad[s].end(); it++) {
if (!vizitat[*it])
DFS_recursiv(*it, vizitat);
}
}
int graf::nr_conexe() {
bool *vizitat = new bool[n];
for (int i = 0; i < n; i++) {
vizitat[i] = false;
}
int nr = 0;
for (int i = 0; i < n; i++) {
if (!vizitat[i]) {
DFS_recursiv(i, vizitat);
nr ++;
}
}
delete[] vizitat;
return nr;
}
int main() {
int n, m, s, a, b;
fin >> n >> m;
graf g(n, 0);
for (int i = 0; i < m; i++) {
fin >> a >> b;
g.adaug_muchie(a-1, b-1);
}
fout << g.nr_conexe();
return 0;
}