Pagini recente » Cod sursa (job #1817232) | Cod sursa (job #1097121) | Cod sursa (job #3222568) | Cod sursa (job #550087) | Cod sursa (job #2854969)
#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 relatedComponents = 0;
void iterateGraph(int currentPeak) {
if (graph[currentPeak].size() == 0 || goneThrough[currentPeak] == 1) {
return;
}
goneThrough[currentPeak] = 1;
for (int i = 0; i < graph[currentPeak].size(); ++i) {
iterateGraph(graph[currentPeak][i]);
}
}
void findConnectedComponents(int currentPeak) {
queue<int> peaks;
if (goneThrough[currentPeak] == 0) {
++relatedComponents;
iterateGraph(currentPeak);
}
/*
peaks.push(currentPeak);
while (!peaks.empty()) {
int currentPeak = peaks.front();
for (int i = 0; i < graph[currentPeak].size(); ++i) {
int nextPeak = graph[currentPeak][i];
if (goneThrough[nextPeak] == 0) {
peaks.push(nextPeak);
goneThrough[nextPeak] = 1;
}
}
peaks.pop();
}
*/
}
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) {
findConnectedComponents(peak);
}
fout << relatedComponents;
return 0;
}
/*
rezolva si recursiv problema (fara coada) si dupa simuleaza recursivitatea intr-un mod iterativ, folosind un stack. Dar a doua parte doar dupa ce faci varianta optima recursiva
Teste:
6 4
1 2
3 2
3 4
5 6 -> 2
6 0 -> 6
1 0 -> 1
6 1
1 2 -> 5
6 5
1 2
2 3
3 4
4 5
5 6 -> 1
6 5
1 2
2 1
3 4
4 3
3 5 -> 3
5 8
1 2
2 1
2 3
3 2
3 4
4 3
1 4
4 1 -> 2
5 9
1 2
2 1
2 3
3 2
3 4
4 3
1 4
4 1
4 5 -> 1
3 2
1 2
3 2 -> 1
{1}
*/