Pagini recente » Cod sursa (job #322658) | Cod sursa (job #1898590) | Cod sursa (job #2330916) | Cod sursa (job #1978932) | Cod sursa (job #322659)
Cod sursa(job #322659)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct{
int cul;
int *vec;
int m;
}Nod;
typedef struct{
int s, d;
}Arc;
#define ALB 0
#define GRI 1
#define NEGRU 2
int *S, vf;
Nod *v;
void DFS(int i)
{
int j, k;
v[i].cul = GRI;
for( j = v[i].m ; j--; ){
k = v[i].vec[j];
if(v[k].cul == ALB)
DFS( k );
}
//S[vf++] = i;
v[i].cul = NEGRU;
}
int main(int argc, char *argv[])
{
//deschidere fisiere
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
//declarare date, initializare, citire si alocare de memorie
Arc *a;
int n, m, i;
scanf("%d%d", &n, &m);
n++;
v = (Nod*)malloc( sizeof(*v) * n );
a = (Arc*)malloc( sizeof(*a) * m );
int *laf, *la;
laf = la = (int*)malloc( sizeof(int) * m<<1 );
S = (int*)malloc( sizeof(int) * n );
for( i = 0; i < n; i++){
v[i].cul = ALB;
v[i].m = 0;
}
for( i = 0; i < m; i++){
scanf("%d%d", &a[i].s, &a[i].d);
v[a[i].s].m++;
v[a[i].d].m++;
}
//crearea listelor de adiacenta
for( i = 0; i < n; i++){
v[i].vec = la;
la += v[i].m;
v[i].m = 0;
}
for( i = 0; i < m; i++){
//for( j = 0; j < v[a[i].s].m; j++)
// if(v[a[i].s].vec[j] == a[i].d)
// continue;
v[a[i].s].vec[v[a[i].s].m++] = a[i].d;
v[a[i].d].vec[v[a[i].d].m++] = a[i].s;
}
vf = 0;
for( i = 1; i < n; i++){
if(v[i].cul == ALB){
//Parcurgere DFS
DFS( i );
vf++;
}
}
printf("%d\n", vf);
//for( i = vf; i--; )
//printf("%d ", S[i]);
//eliberare memorie
free( a );
free( v );
free( S );
free( laf );
return 0;
}