Pagini recente » Cod sursa (job #2589717) | Cod sursa (job #1925636) | Cod sursa (job #3255993) | Cod sursa (job #628971) | Cod sursa (job #2878733)
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <queue>
#include <stack>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
const int MAX_SIZE = 200005;
vector<int> graph[MAX_SIZE];
int goneThrough[MAX_SIZE], relatedComponents = 0;
void markComponent(int startPeak) {
goneThrough[startPeak] = 1;
stack<int> positions;
positions.push(startPeak);
while (!positions.empty()) {
int currentPeak = positions.top();
positions.pop();
for (int i = 0; i < graph[currentPeak].size(); ++i) {
if (goneThrough[graph[currentPeak][i]] == 0) {
positions.push(graph[currentPeak][i]);
goneThrough[graph[currentPeak][i]] = 1;
}
}
}
}
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);
graph[end].push_back(start);
}
for (int peak = 1; peak <= peaks; ++peak) {
if (goneThrough[peak] == 0) {
++relatedComponents;
markComponent(peak);
}
}
fout << relatedComponents;
return 0;
}