Pagini recente » Cod sursa (job #3125403) | Cod sursa (job #1090550) | Cod sursa (job #135286) | Cod sursa (job #2604620) | Cod sursa (job #2242250)
#include <iostream>
#include <fstream>
#define nmax 100100
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int n, m, vis[nmax];
struct nod {
int info;
nod *urm;
}*a[nmax];
void Adauga(int n1, int n2) {
if (a[n1] == NULL) {
a[n1] = new nod();
a[n1]->info = n2;
a[n1]->urm = NULL;
} else {
nod *aux = a[n1];
while (aux->urm != NULL) {
aux = aux->urm;
}
aux->urm = new nod();
aux = aux->urm;
aux->info = n2;
aux->urm = NULL;
}
}
void citire() {
f >> n >> m;
int x, y;
for (int i = 1;i <= m;i ++) {
f >> x >> y;
Adauga(x, y);
Adauga(y ,x);
}
}
void DFS(int x) {
vis[x] = 1;
nod * aux = a[x];
while (aux != NULL) {
int vCurr = aux->info;
if (vis[vCurr] == 0) {
DFS(vCurr);
}
aux = aux->urm;
}
}
void rez() {
int Answer = 0;
for (int i = 1;i <= n;i ++) {
if (vis[i] == 0 ) {
//cout << i << " ";
Answer ++;
DFS(i);
}
}
g << Answer;
}
void afiseaza(int x) {
nod * aux = a[x];
while (aux != NULL) {
cout << aux->info << " ";
aux = aux->urm;
}
}
int main() {
citire();
//afiseaza(1);
rez();
return 0;
}