Pagini recente » Cod sursa (job #2714447) | Cod sursa (job #2412632) | Cod sursa (job #1466547) | Cod sursa (job #2687255) | Cod sursa (job #1699407)
#include <stdio.h>
#include <stdlib.h>
#define Nadejde 100000
typedef struct {
int v, next;
} list;
int N, M, buff;
list *l;
int adj[Nadejde + 1];
char seen[Nadejde + 1];
void alloc() {
l = (list*)calloc(2 * M + 1, sizeof(list));
}
void addEdge(int u, int v) {
buff++;
l[buff].v = v;
l[buff].next = adj[u];
adj[u] = buff;
}
/** Exploreaza recursiv graful. **/
void dfs(int u) {
int pos;
if (!seen[u]) {
seen[u] = 1;
for (pos = adj[u]; pos; pos = l[pos].next) {
dfs(l[pos].v);
}
}
}
int main(void) {
int i, u, v;
FILE *f = fopen("dfs.in", "r");
/* Citirea datelor. */
fscanf(f, "%d %d", &N, &M);
alloc();
for (i = 1; i <= M; i++) {
fscanf(f, "%d %d", &u, &v);
addEdge(u, v);
addEdge(v, u);
}
fclose(f);
/* Calcularea solutiei. */
int numSeen = 0;
for (u = 1; u <= N; u++) {
if (!seen[u]) {
dfs(u);
numSeen++;
}
}
/* Afisarea solutiei. */
freopen("dfs.out", "w", stdout);
fprintf(stdout, "%d\n", numSeen);
fclose(stdout);
/// Multumim Doamne!
puts("Doamne ajuta!");
return 0;
}