Pagini recente » Cod sursa (job #725876) | Cod sursa (job #533897) | Cod sursa (job #2103479) | Cod sursa (job #1693302) | Cod sursa (job #503145)
Cod sursa(job #503145)
#include<stdio.h>
#include<stdlib.h>
int mask[100001];
struct list* edges[100001];
int N, M, count = 0;
struct list {
int data;
struct list* next;
};
void DFS(int x) {
if(mask[x] == 0) {
count++;
mask[x] = count;
}
struct list *p = edges[x];
while(p != NULL) {
if(mask[p->data] == 0) {
mask[p->data] = count;
DFS(p->data);
}
p = p->next;
}
}
int main() {
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
int i;
scanf("%d%d", &N, &M);
for(i = 1; i<=N; i++) {
mask[i] = count;
edges[i] = NULL;
}
int x,y;
for(i = 1; i<=M; i++) {
struct list *a, *b;
scanf("%d%d", &x, &y);
a = (struct list*)malloc(sizeof(struct list));
a->data = y;
a->next = edges[x];
edges[x] = a;
b = (struct list*)malloc(sizeof(struct list));
b->data = x;
b->next = edges[y];
edges[y] = b;
}
for(i = 1; i<=N; i++) {
DFS(i);
}
printf("%d\n", count);
return 0;
}