Pagini recente » Cod sursa (job #2592675) | Cod sursa (job #2724020) | Cod sursa (job #2783033) | Cod sursa (job #2596884) | Cod sursa (job #1278788)
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 100000
int nodVizitat[MAX_N+1];
typedef struct lista {
int nod;
struct lista *urm;
} lista;
lista *g[MAX_N+1];
void adauga(int i, int j) {
lista *p = malloc( sizeof(lista) );
p -> nod = j;
p -> urm = g[i];
g[i] = p;
}
void citesteGraf(int muchii, FILE *in) {
int i, a, b;
for ( i = 1; i <= muchii; i++ ) {
fscanf(in, "%d %d", &a, &b);
adauga(a,b);
adauga(b,a);
}
}
void DFS(int nod) {
lista *p;
nodVizitat[nod] = 1;
for ( p = g[nod]; p != NULL; p = p -> urm )
if ( !nodVizitat[ p -> nod ] )
DFS(p -> nod);
}
int main()
{
FILE *in = fopen("dfs.in","r");
FILE *out = fopen("dfs.out", "w");
int muchii, noduri;
fscanf(in,"%d %d",&noduri,&muchii);
citesteGraf(muchii,in);
int i, contor = 0;
for ( i = 1; i <= noduri; i++ ) {
if ( !nodVizitat[i] ) {
contor++;
DFS(i);
}
}
fprintf(out,"%d",contor);
fclose(in);
fclose(out);
return 0;
}