Pagini recente » Cod sursa (job #2322713) | Cod sursa (job #153661) | Cod sursa (job #307295) | Cod sursa (job #363264) | Cod sursa (job #2850778)
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <queue>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
const int MAX_SIZE = 2 * 100005;
vector<int> graph[MAX_SIZE];
int goneThrough[MAX_SIZE];
int totalComponents = 0;
void DFS(int currentPeak) {
queue<int> positions;
int ok = 0;
positions.push(currentPeak);
if (goneThrough[currentPeak] == 0) {
goneThrough[currentPeak] = 1;
ok = 1;
}
while (!positions.empty()) {
int currentPeak = positions.front();
for (int i = 0; i < graph[currentPeak].size(); ++i) {
int nextPoint = graph[currentPeak][i];
if (goneThrough[nextPoint] == 0) {
positions.push(nextPoint);
goneThrough[nextPoint] = 1;
}
}
positions.pop();
}
if (ok) {
++totalComponents;
}
}
int main() {
int peaks, arches;
fin >> peaks >> arches;
for (int i = 1; i <= arches; ++i) {
int start, end;
fin >> start >> end;
graph[start].push_back(end);
}
for (int j = 1; j <= peaks; ++j) {
DFS(j);
}
fout << totalComponents;
return 0;
}
/*
Ideea: avem un array pentru a marca daca am trecut deja prin punctul respectiv.
Ne folosim de o coada pentru a adauga elementele noi.
Cand coada e goala si daca am parcurs vreun element, adunam cu 1 componentele conexe
*/