Pagini recente » Cod sursa (job #1889937) | Cod sursa (job #917020) | Cod sursa (job #2430082) | Cod sursa (job #2387609) | Cod sursa (job #1431155)
#include <stdio.h>
#include <stdlib.h>
#include <vector>
using namespace std;
typedef struct graph {
int nr_varfuri;
int nr_varfuri_nevizitate;
bool* vizitat;
vector<vector<int> > vectori;
int nr;
int** matrice;
}*Graph;
Graph initGraph(int nr_varfuri) {
Graph g;
g = (Graph) malloc(sizeof(struct graph));
g->nr_varfuri = nr_varfuri;
g->nr_varfuri_nevizitate = nr_varfuri;
g->vizitat = (bool*) calloc(nr_varfuri, sizeof(bool));
g->matrice = (int**) malloc(nr_varfuri*sizeof(int*));
vector<int> vect;
for(int i = 0; i < nr_varfuri; i++) {
g->vectori.push_back(vect);
g->matrice[i] = (int*) malloc(nr_varfuri*sizeof(int));
g->vizitat[i] = false;
for(int j = 0; j < nr_varfuri; j++) {
g->matrice[i][j] = 0;
}
}
g->nr = 0;
return g;
}
Graph addEdge(Graph g, int u, int v) {
g->matrice[u][v] = 1;
g->matrice[v][u] = 1;
return g;
}
Graph readGraph() {
int nr_varfuri, rez, x, y;
scanf("%d", &nr_varfuri);
Graph g = initGraph(nr_varfuri+1);
rez = scanf("%d %d", &x, &y);
while(rez > 0) {
g = addEdge(g, x, y);
rez = scanf("%d %d", &x, &y);
}
return g;
}
void dfs(Graph g, int src) {
g->vizitat[src] = true;
g->vectori[g->nr].push_back(src);
g->nr_varfuri_nevizitate--;
for(int i = 1; i < g->nr_varfuri; i++) {
if(g->matrice[src][i] && !g->vizitat[i]) {
dfs(g, i);
}
}
}
int main() {
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
Graph g;
g = readGraph();
for(int i = 1; i < g->nr_varfuri; i++) {
if(g->nr_varfuri_nevizitate == 0) {
break;
}
dfs(g, i);
g->nr++;
}
printf("%d\n", g->nr);
return 0;
}