Pagini recente » Cod sursa (job #2225269) | Cod sursa (job #2616163) | Cod sursa (job #695074) | Cod sursa (job #3042094) | Cod sursa (job #1700666)
#include <stdio.h>
#define MAX_NODURI 100000
#define MAX_MUCHII 200000
int start[1+MAX_NODURI];
int last[1+MAX_NODURI];
int next[1+MAX_MUCHII*2];
int muchie[1+MAX_MUCHII*2];
int fol[1+MAX_NODURI];
void insertMuchie(int i, int a, int b) {
if(start[a] == 0)
start[a] = last[a] = i;
else
last[a] = next[last[a]] = i;
muchie[i] = b;
}
void fill(int nod) {
int i;
fol[nod] = 1;
i = start[nod];
while(i != 0) {
if(!fol[muchie[i]])
fill(muchie[i]);
i = next[i];
}
}
int main() {
int n, m, a, b, i, componente;
FILE *fin = fopen( "dfs.in" , "r" );
fscanf(fin, "%d%d", &n, &m);
for(i = 1; i <= m; i++) {
fscanf(fin, "%d%d", &a, &b);
insertMuchie(2 * i - 1, a, b);
insertMuchie(2 * i, b, a);
}
fclose( fin );
componente = 0;
for(i = 1; i <= n; i++)
if(!fol[i]) {
fill(i);
componente++;
}
FILE *fout = fopen( "dfs.out" , "w" );
fprintf(fout, "%d", componente);
fclose( fout );
return 0;
}