Cod sursa(job #2850821)

Utilizator CiuiGinjoveanu Dragos Ciui Data 17 februarie 2022 16:34:04
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.71 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 DFS(int currentPeak) {
    queue<int> peaks;
    int ok = 0;
    peaks.push(currentPeak);
    if (goneThrough[currentPeak] == 0) {
        goneThrough[currentPeak] = 1;
        ok = 1;
    }
    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();
    }
    if (ok) {
        ++relatedComponents;
    }
}

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 j = 1; j <= peaks; ++j) {
        DFS(j);
    }
    fout << relatedComponents;
    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
 
 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

 
 
 */