Pagini recente » Rating Antonia Haller (betiteb) | Cod sursa (job #1161463) | Cod sursa (job #1861425) | Cod sursa (job #2245012) | Cod sursa (job #2202119)
#include <stdio.h>
#include <stdlib.h>
#define Max 1000
int n, m, viz[Max], nr;
int *adia[Max];
void initializare();
void citire();
void dfs(int s);
void afisare();
void componente_conexe();
int main(){
citire();
//afisare();
componente_conexe();
return 0;
}
void citire(){
FILE* f = fopen("dfs.in", "r");
fscanf(f, "%d%d", &n, &m);
int x, y;
for(int i = 1; i <= n; i++){
adia[i] = (int* )realloc(adia[i], sizeof(int));
adia[i][0] = 0;
}
for(int i = 0; i < m; i++){
fscanf(f, "%d%d", &x, &y);
adia[x][0]++;
adia[x] = (int* )realloc(adia[x], (adia[x][0])*sizeof(int));
adia[x][adia[x][0]] = y;
adia[y][0]++;
adia[y] = (int* )realloc(adia[y], (adia[y][0])*sizeof(int));
adia[y][adia[y][0]] = x;
}
fclose(f);
}
void initializare(){
for(int i = 1; i <= n; i++)
viz[i] = 0;
}
void dfs(int s){
int i;
//printf("%d ", s);
viz[s] = 1;
for(i = 1; i <= adia[s][0]; i++)
if(!viz[adia[s][i]])
dfs(adia[s][i]);
}
void afisare(){
FILE* f = fopen("dfs.out", "w");
for(int i = 1; i <= n; i++){
for(int j = 1; j <= adia[i][0]; j++)
fprintf(f, "%d ", adia[i][j]);
fprintf(f, "\n");
}
}
void componente_conexe(){
for(int i = 1; i <= n; i++)
if(viz[i] == 0){
nr++;
dfs(i);
}
FILE* f = fopen("dfs.out", "w");
fprintf(f, "%d", nr);
}