Pagini recente » Cod sursa (job #2306842) | Cod sursa (job #3125774) | Cod sursa (job #2723437) | Cod sursa (job #2123915) | Cod sursa (job #1277711)
#include <cstdio>
#include <vector>
using namespace std;
FILE *fin, *fout;
#define NMAX 100005
bool visited[NMAX];
void dfs (int node, vector <vector<int> > &graf) {
int ls = graf[node].size(), i, vf;
visited[node] = 1;
for (i=0; i<ls; ++i) {
vf = graf[node][i];
if (!visited[vf])
dfs (vf, graf);
}
}
int main() {
fin = fopen ("dfs.in", "r");
fout = fopen ("dfs.out", "w");
int n, m, i, a, b, cc=0;
fscanf (fin, "%d%d", &n, &m);
vector <vector<int> > graf (n);
for (i=1; i<=m; ++i) {
fscanf (fin, "%d%d", &a, &b);
graf[a].push_back(b);
graf[b].push_back(a);
}
for (i=1; i<=n; ++i)
if (!visited[i]) {
dfs(i, graf);
++cc;
}
fprintf (fout, "%d\n", cc);
fclose(fin); fclose(fout);
return 0;
}