Pagini recente » Cod sursa (job #11012) | Cod sursa (job #2570635) | Cod sursa (job #1140427) | Cod sursa (job #1196762) | Cod sursa (job #1447702)
#include <stdio.h>
#include <stdlib.h>
typedef struct{
int nn;
int** x;
} TGV, *AGV;
AGV init(int n, int m);
void ins(AGV g, int s, int d);
void auxdfs(AGV g, int a, int* v);
int dfs(AGV g, int* v);
int main(){
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
AGV 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, m);
if(!graf) return 0;
for(i = 0; i < m; i++){
scanf("%d%d", &s, &d);
ins(graf, s, d);
}
printf("%d\n", dfs(graf, v));
return 0;
}
AGV init(int n, int m){
AGV g = (AGV)malloc(sizeof(TGV));
if(!g) return NULL;
g->x = (int**)malloc((n + 2) * sizeof(int*));
if(!g->x){
free(g);
return NULL;
}
g->x[1] = (int*)malloc(m * sizeof(int));
if(!g->x[1]){
free(g->x);
free(g);
return NULL;
}
g->nn = n;
int i;
for(i = 2; i <= n + 1; i++)
g->x[i] = g->x[1];
return g;
}
void ins(AGV g, int s, int d){
if(s > g->nn) return;
*g->x[s + 1] = d;
int i;
for(i = s + 1; i <= g->nn + 1; i++)
g->x[i]++;
}
void auxdfs(AGV g, int a, int* v){
int* i;
if(v[a]) return;
v[a] = 1;
for(i = g->x[a]; i < g->x[a + 1]; i++)
auxdfs(g, *i, v);
}
int dfs(AGV g, int* v){
int i, cnt = 0;;
for(i = 1; i <= g->nn; i++)
if(!v[i]){
cnt++;
auxdfs(g, i, v);
}
return cnt;
}