Pagini recente » Cod sursa (job #2160947) | Cod sursa (job #1249718) | Monitorul de evaluare | Cod sursa (job #1462542) | Cod sursa (job #1451584)
#include <stdio.h>
#include <stdlib.h>
typedef struct cel{
int info;
struct cel* urm;
} TCel, *TLista, **ALista;
typedef struct{
int nn;
ALista x;
} TGL, *AGL;
AGL init(int n);
void ins(AGL g, int s, int d);
void auxdfs(AGL g, int a, int* v);
int dfs(AGL g, int* v);
int main(){
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
AGL graf;
int n, m, i, s, d;
int *v;
scanf("%d%d", &n, &m);
v = (int*)calloc(n + 1, sizeof(int));
if(!v) return 0;
graf = init(n);
if(!graf) return 0;
for(i = 0; i < m; i++){
scanf("%d%d", &s, &d);
ins(graf, s, d);
}
//afis(graf);
printf("%d\n", dfs(graf, v));
free(v);
return 0;
}
AGL init(int n){
AGL g = (AGL)malloc(sizeof(TGL));
if(!g) return NULL;
g->x = (ALista)calloc(n + 1, sizeof(TLista));
if(!g->x){
free(g);
return NULL;
}
g->nn = n;
return g;
}
void ins(AGL g, int s, int d){
TLista aux1 = (TLista)malloc(sizeof(TCel));
if(!aux1) return;
aux1->info = d;
aux1->urm = g->x[s];
g->x[s] = aux1;
TLista aux2 = (TLista)malloc(sizeof(TCel));
if(!aux2) return;
aux2->info = s;
aux2->urm = g->x[d];
g->x[d] = aux2;
}
void auxdfs(AGL g, int a, int* v){
if(v[a]) return;
//printf("%d\n", a);
v[a] = 1;
TLista l = g->x[a];
while(l){
auxdfs(g, l->info, v);
l = l->urm;
}
}
int dfs(AGL g, int* v){
int i, cnt = 0;
for(i = 1; i <= g->nn; i++)
if(!v[i]){
cnt++;
auxdfs(g, i, v);
}
return cnt;
}