Pagini recente » Borderou de evaluare (job #2800586) | Borderou de evaluare (job #3154152) | Borderou de evaluare (job #1768587) | Borderou de evaluare (job #1369596) | Cod sursa (job #1988778)
#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);
}
}
int main() {
readData();
int nrC = 1;
for(int i = 1; i<=n; i++)
if(!viz[i]) {
nrC ++;
bfs(i);
}
printf("%d", nrC);
return 0;
}