Pagini recente » Cod sursa (job #2224059) | Cod sursa (job #3204203) | Cod sursa (job #1891687) | Cod sursa (job #2576614) | Cod sursa (job #1480470)
#include <stdio.h>
#define Smerenie 200001
#define Nadejde 100001
typedef struct {
int v, next;
} list;
int N, M;
int adj[Nadejde]; // capetele listelor de adiacenta.
list l[Smerenie]; // lista muchiilor alocata static.
char seen[Nadejde];
/** Adauga-l pe "v" la lista de adiacenta a lui "u". **/
void addEdge(int u, int v, int pos) {
l[pos].v = v;
l[pos].next = adj[u];
adj[u] = pos;
}
/** Parcurge recursiv nodul "u". **/
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);
}
}
}
/** Afla numarul de componente conexe ale grafului. **/
int conex() {
int u, count = 0;
for (u = 1; u <= N; u++) {
if (!seen[u]) {
dfs(u);
count++;
}
}
return count;
}
int main(void) {
int i, u, v;
FILE *f = fopen("dfs.in", "r");
/* Citeste graful. */
fscanf(f, "%d %d", &N, &M);
for (i = 1; i <= M; i++) {
fscanf(f, "%d %d", &u, &v);
addEdge(u, v, i);
addEdge(v, u, i + M);
}
fclose(f);
f = fopen("dfs.out", "w");
fprintf(f, "%d\n", conex());
fclose(f);
/// Multumim Doamne!
puts("Doamne ajuta!");
return 0;
}