Cod sursa(job #2878733)

Utilizator CiuiGinjoveanu Dragos Ciui Data 27 martie 2022 15:06:22
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#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;
}