Pagini recente » Cod sursa (job #2640076) | Cod sursa (job #1087532) | Cod sursa (job #2826262) | Cod sursa (job #1215343) | Cod sursa (job #1699428)
#include <bits/stdc++.h>
#define Nadejde 100000
#define NIL -1
struct nod {
int val;
nod *urm;
};
class list {
private:
nod* l;
public:
list() {
l = NULL;
}
/** Adauga valoarea "x" in lista. **/
void push_back(int x) {
nod* nou = new nod;
nou -> val = x;
nou -> urm = l;
l = nou;
}
nod* begin() {
return l;
}
};
int N, M, buff;
list adj[Nadejde + 1];
char seen[Nadejde + 1];
void addEdge(int u, int v) {
adj[u].push_back(v);
}
/** Exploreaza recursiv graful. **/
void dfs(int u) {
nod *it;
if (!seen[u]) {
seen[u] = 1;
for (it = adj[u].begin(); it != NULL; it = it -> urm) {
dfs(it -> val);
}
}
}
int main(void) {
int i, u, v;
FILE *f = fopen("dfs.in", "r");
/* Citirea datelor. */
fscanf(f, "%d %d", &N, &M);
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;
}