Pagini recente » Cod sursa (job #1129015) | Cod sursa (job #2062421) | Cod sursa (job #469403) | Cod sursa (job #833841) | Cod sursa (job #2909754)
#include <iostream>
#include <vector>
using namespace std;
#define MAX_N 100000
struct Node {
int subset;
vector<int> edges;
};
Node nodes[MAX_N];
void addEdge(int a, int b) {
nodes[a].edges.push_back(b);
nodes[b].edges.push_back(a);
}
void dfs(int nodeIndex, int subset) {
nodes[nodeIndex].subset = subset;
for (int neighbour : nodes[nodeIndex].edges)
if (nodes[neighbour].subset != subset)
dfs(neighbour, subset);
}
int main() {
FILE *fin, *fout;
fin = fopen("dfs.in", "r");
fout = fopen("dfs.out", "w");
int n, m, i, a, b, noSubsets;
fscanf(fin, "%d%d", &n, &m);
for (i = 0; i < m; ++i) {
fscanf(fin, "%d%d", &a, &b);
addEdge(a, b);
}
noSubsets = 0;
for (i = 0; i < n; ++i)
if (nodes[i].subset == 0)
dfs(i, ++noSubsets);
fprintf(fout, "%d", noSubsets);
fclose(fin);
fclose(fout);
return 0;
}