Pagini recente » Cod sursa (job #1412492) | Cod sursa (job #1141415) | Cod sursa (job #55523) | Cod sursa (job #2832460) | Cod sursa (job #2763016)
#include <fstream>
#include <iostream>
#include <bitset>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
struct nodd {
int value;
nodd *next;
};
void add_begin(nodd *&L, int integer) {
nodd *aux = new nodd;
aux->value = integer;
aux->next = L;
L = aux;
}
void display(nodd *L) {
while (L != nullptr) {
fout << L->value << " ";
L = L->next;
}
fout << endl;
}
int n, m, ct;
bitset<100010> viz;
void dfs(int);
nodd *L[] ={};
int main() {
fin >> n >> m;
for (; m != 0; m--) {
int x, y;
fin >> x >> y;
add_begin(L[x], y);
add_begin(L[y], x);
}
/*
display(L[1]);
display(L[2]);
display(L[3]);
display(L[4]);
display(L[5]);
fout<<endl<<endl;
for(int i=1;i<=5;i++) {
while (L[i] != nullptr) {
fout << L[i]->value;
L[i] = L[i]->next;
}
fout<<endl;
}
*/
for (int i = 1; i <= n; i++)
if (!viz[i]) {
viz[i] = true;
dfs(i);
ct++;
}
//fout<<"am trecut de for\n";
fout << ct;
return 0;
}
void dfs(int nod_cur) {
while (L[nod_cur] != nullptr) {
viz[L[nod_cur]->value] = true;
L[nod_cur] = L[nod_cur]->next;
dfs(L[nod_cur]->value);
}
}