Pagini recente » Cod sursa (job #1094094) | Cod sursa (job #1314215) | Cod sursa (job #2927351) | Cod sursa (job #2823453) | Cod sursa (job #2519451)
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int nrcomp, frecv[250000];
int vertices, edges;
vector<int> gr[250000];
void DFS(int nod) {
frecv[nod] = nrcomp;
for (int i = 0; i < gr[nod].size(); i++)
if (!frecv[i])
DFS(i);
}
void comp() {
for (int i = 0; i < edges; i++)
if (frecv[i] == 0) {
nrcomp++;
DFS(i);
}
}
int main(int argc, const char * argv[]) {
fin >> vertices >> edges;
for (int i = 0; i < edges; i++) {
int x, y;
fin >> x >> y;
gr[x].push_back(y);
gr[y].push_back(x);
}
comp();
fout << nrcomp;
}