Pagini recente » Cod sursa (job #2230550) | Cod sursa (job #3167952) | Cod sursa (job #3282576) | Cod sursa (job #1243392) | Cod sursa (job #2978087)
#include <stdio.h>
#include <map>
#include <list>
using namespace std;
int n, m, x, y;
map<int, list<int>> adj;
map<int, bool> visited;
FILE *in, *out;
void dfs(int start) {
if (!visited[start]) visited[start] = true;
for (auto neigh : adj[start])
if (!visited[neigh]) {
visited[neigh] = true;
dfs(neigh);
}
}
int main() {
int rez = 0;
in = fopen("dfs.in", "r");
out = fopen("dfs.out", "w");
fscanf(in, "%d %d", &n, &m);
// create adjacency lists
for (int i = 0; i < m; i++) {
fscanf(in, "%d %d", &x, &y);
adj[x].push_back(y);
adj[y].push_back(x);
}
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
rez++;
dfs(i);
}
}
fprintf(out, "%d", rez);
fclose(in);
fclose(out);
return 0;
}