Cod sursa(job #2854969)

Utilizator CiuiGinjoveanu Dragos Ciui Data 21 februarie 2022 21:35:34
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.01 kb
#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}
 */