Pagini recente » Cod sursa (job #2822447) | Cod sursa (job #2375014) | Cod sursa (job #2727936) | Cod sursa (job #1982499) | Cod sursa (job #2858391)
#include <stdio.h>
#include <vector>
#define N 100000
using namespace std;
vector <int> g[N + 1];
int comp[N + 1];
int n;
void dfs(int node) {
for (const int& vecin : g[node]) {
if ( comp[vecin] == 0) {
comp[vecin] = comp[node];
dfs(vecin);
}
}
}
inline void addMuchie(int a, int b) {
g[a].push_back(b);
g[b].push_back(a);
}
FILE *in, *out;
in = fopen("dfs.in", "r");
out = fopen("dfs.out", "w");
int main() {
int m, a, b;
fscanf( in, "%d%d", &n, &m);
for (int i = 0; i < m; i ++) {
fscanf(in, "%d%d", &a, &b);
addMuchie(a, b);
}
int nr = 0;
for (int i = 1; i <= n; i ++) {
if (comp[i] == 0) {
nr ++;
comp[i] = nr;
dfs(i);
}
}
fprintf(out, "%d\n", nr);
return 0;
}