Pagini recente » Cod sursa (job #1874456) | Monitorul de evaluare | Cod sursa (job #1528112) | Cod sursa (job #2014704) | Cod sursa (job #2594857)
#include <stdio.h>
#include <stdbool.h>
int vf[400001], urm[400001], lst[100001];
int nr;
bool visited[100001];
void add(int x, int y) {
vf[++nr] = y;
urm[nr] = lst[x];
lst[x] = nr;
}
void dfs(int x) {
visited[x] = true;
int y;
for (int p = lst[x]; p != 0; p = urm[p]) {
y = vf[p];
if (visited[y] == false) {
dfs(y);
}
}
}
int main() {
FILE *fin, *fout;
int n, m, comp;
fin = fopen("dfs.in", "r");
fscanf(fin, "%d%d", &n, &m);
for (int i = 0; i < m; i++) {
int a, b;
fscanf(fin, "%d%d", &a, &b);
add(a, b);
add(b, a);
}
fclose(fin);
comp = 0;
for (int i = 1; i <= n; i++) {
if (visited[i] == false) {
dfs(i);
comp++;
}
}
fout = fopen("dfs.out", "w");
fprintf(fout, "%d", comp);
fclose(fout);
return 0;
}