Pagini recente » Cod sursa (job #1018380) | Monitorul de evaluare | Rating Sabina Brasoveanu (sabinab) | Cod sursa (job #2979989) | Cod sursa (job #2683467)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
int N, M, X, Y,cnt;
int viz[100005];
struct nod {
int x;
nod* next;
};
nod* v[100005];
void add(nod*& dest, int val){
nod* p;
p = new nod;
p->x = val;
p->next = dest;
dest = p;
}
void DFS(int curentNod) {
nod* p;
viz[curentNod] = 1;
for ( p = v[curentNod]; p != NULL; p = p->next)
if (!viz[p->x])
DFS(p->x);
}
int main() {
in >> N >> M;
for (int i = 0; i < N; ++i) {
in >> X >> Y;
add(v[X], Y);
add(v[Y], X);
}
for (int i = 1; i <= N; i++)
if (!viz[i]) { cnt++; DFS(i); }
out << cnt;
in.close();
out.close();
return 0;
}