Pagini recente » Borderou de evaluare (job #2758598) | Cod sursa (job #1200756) | Borderou de evaluare (job #2539904) | Borderou de evaluare (job #2057079) | Cod sursa (job #1988779)
#include <cstdio>
#define NMAX 100001
using namespace std;
FILE *f = freopen("dfs.in", "r", stdin);
FILE *g = freopen("dfs.out", "w", stdout);
struct nod{
int vecin;
nod *urmator;
};
nod *a[NMAX]; ///vector de pointeri, fiecare element a[i] reprezinta 'capul' listei de vecini ai nodului i
int coada[NMAX], p, u, n, m;
bool viz[NMAX];
void insertBeginning(nod *& head, int val) {
nod *tmp = new nod;
tmp -> vecin = val;
tmp -> urmator = head;
head = tmp;
}
void afisare(nod *& head) {
nod *tmp = head;
while(tmp != NULL) {
printf("%d ", tmp -> vecin);
tmp = tmp -> urmator;
}
}
void bfs(int start) {
viz[start] = true;
p = u = 1;
coada[p] = start;
while(p <= u) {
int node = coada[p];
nod *head = a[node];
while(head != NULL) {
if(!viz[head -> vecin]) {
viz[head -> vecin] = true;
u ++;
coada[u] = head -> vecin;
}
head = head -> urmator;
}
p ++;
}
}
void readData() {
scanf("%d%d", &n, &m);
for(int i = 1; i<=m; i++) {
int x, y;
scanf("%d%d", &x, &y);
insertBeginning(a[x], y);
insertBeginning(a[y], x);
}
}
int main() {
readData();
/*for(int i = 1; i<=n; i++) {
printf("Vecinii nodului %d sunt ", i);
afisare(a[i]);
printf("\n");
}*/
int nrC = 0;
for(int i = 1; i<=n; i++)
if(!viz[i]) {
nrC ++;
bfs(i);
}
printf("%d", nrC);
return 0;
}