Pagini recente » Cod sursa (job #997626) | Cod sursa (job #1208941) | Cod sursa (job #465030) | Cod sursa (job #1938588) | Cod sursa (job #1844116)
#include <fstream>
#include <vector>
#include <iostream>
#define NMax 100000
#define MMax (NMax * (NMax - 1) / 2)
void read(int &n, std::vector < int > v[]) {
int k, x, y;
std::ifstream fin("dfs.in");
fin >> n >> k;
for (int i = 0; i < k; i++) {
fin >> x >> y;
v[x - 1].push_back(y - 1);
v[y - 1].push_back(x - 1);
}
fin.close();
}
void DFS(int n, std::vector < int > v[], int c[], int x, int nrCnt) {
c[x] = nrCnt;
for (int i = 0; i < v[x].size(); i++) {
if (c[v[x][i]] == 0) {
DFS(n, v, c, v[x][i], nrCnt);
}
}
}
void solve(int n, std::vector < int > v[], int c[], int &nrCnt) {
for (int i = 0; i < n; i++) {
if (!c[i]) {
nrCnt++;
DFS(n, v, c, i, nrCnt);
}
}
}
int main(int argc, char *argv[]) {
int n, c[NMax] = { 0 }, nrCnt = 0;
std::vector < int > v[NMax];
read(n, v);
solve(n, v, c, nrCnt);
std::ofstream fout("dfs.out");
fout << nrCnt;
fout.close();
return 0;
}