Pagini recente » Cod sursa (job #2207842) | Cod sursa (job #2879535) | Cod sursa (job #3170913) | Cod sursa (job #1787077) | Cod sursa (job #1431167)
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <iostream>
#include <set>
#include <queue>
#include <stack>
#define LUNG_MAX 500000
using namespace std;
typedef struct graph {
vector<vector<pair<int, int> > > lists;
int nrNoduri;
int nrMuchii;
bool *vizitat;
int *cost_minim;
}*Graph;
Graph initGraph(int nrNoduri, int nrMuchii) {
Graph graf = (Graph) malloc(sizeof(struct graph));
graf->nrNoduri = nrNoduri;
graf->nrMuchii = nrMuchii;
graf->vizitat = (bool*) calloc(nrNoduri,sizeof(bool));
graf->cost_minim = (int*) malloc(nrNoduri*sizeof(int));
for(int i = 0; i < nrNoduri; i++) {
graf->vizitat[i] = false;
graf->cost_minim[i] = -1;
vector<pair<int, int> > lista;
graf->lists.push_back(lista);
}
return graf;
}
Graph addEdge(Graph graf, int u, int v, int cost) {
graf->lists[u].push_back(make_pair(v, cost));
return graf;
}
vector<pair<int, int> > getList(Graph graf, int u) {
return graf->lists[u];
}
void dfs(Graph &graf, int source) {
graf->vizitat[source] = true;
for(int i = 0; i < graf->lists[source].size(); i++) {
int v = graf->lists[source].at(i).first;
if(graf->vizitat[v] == false) {
dfs(graf, v);
}
}
}
void componente_conexe(Graph graf) {
int nr = 0;
for(int i = 1; i < graf->nrNoduri; i++) {
if(graf->vizitat[i] == false) {
dfs(graf, i);
nr++;
}
}
printf("%d\n", nr);
}
int main() {
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
int N, M, S, i, u, v;
scanf("%d %d", &N, &M);
Graph graf = initGraph(N+1, M);
for(i = 0; i < M; i++) {
scanf("%d %d", &u, &v);
graf = addEdge(graf, u, v, 1);
graf = addEdge(graf, v, u, 1);
}
componente_conexe(graf);
return 0;
}