Pagini recente » Cod sursa (job #2868712) | Cod sursa (job #3157874) | Cod sursa (job #914408) | Cod sursa (job #2081715) | Cod sursa (job #815710)
Cod sursa(job #815710)
#include <fstream>
#define NMAX 100001
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int N, M, nrConex;
int U[NMAX];
struct list {
int info;
list *next;
} *G[NMAX];
// graf neorientat
void add(int a, int b) {
list *q = new list;
q->info = b;
q->next = G[a];
G[a] = q;
}
void dfs(int source) {
U[source] = 1;
list *p;
for(p = G[source]; p; p = p->next)
if(!U[p->info]) dfs(p->info);
}
int main() {
int i, a, b;
fin >> N >> M;
for(i = 1; i <= M; ++ i) {
fin >> a >> b;
add(a, b);
add(b, a);
}
for(i = 1; i <= N; ++ i)
if(!U[i]) ++ nrConex, dfs(i);
fout << nrConex << '\n';
return 0;
}