Pagini recente » Cod sursa (job #2297633) | Cod sursa (job #2407874) | Cod sursa (job #723111) | Cod sursa (job #1446024) | Cod sursa (job #2419926)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int N, M;
vector<vector<int>> graf;
vector<bool> vizitate;
int conexe = 0;
void dfs(int n);
int main() {
fstream fin("dfs.in", ios::in);
fstream fout("dfs.out", ios::out);
int x, y;
// citesc N,M
fin >> N >> M;
// initializare linii graf
vector<int> a;
graf.assign(N, a);
// initializare vizitate
vizitate.assign(N, false);
// citire graf
for (int i = 0; i < M; i++) {
fin >> x >> y;
(graf[x-1]).push_back(y-1);
}
// parcurgere dfs
for (int i = 0; i < N; i++) {
if (false == vizitate[i]) {
conexe++;
dfs(i);
}
}
// afisare
fout << conexe;
// close
fin.close();
fout.close();
}
void dfs(int n) {
vizitate[n] = true;
vector<int>& linie = graf[n];
for (auto& i:linie) {
if (vizitate[i]==false)
dfs(i);
}
}