Cod sursa(job #3169929)

Utilizator dragos1029Dragos Morar dragos1029 Data 16 noiembrie 2023 12:42:42
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");

const int N_MAX = 100000;

struct Nod {
    bool vizitat = false;
    int indexComponentConex = -1;
    vector<int> indexVecini;
};

int N, M, nrComponenteConexe = 0;
Nod noduri[N_MAX];
stack<int> dfsStack;

void citire() {
    fin >> N >> M;
    int outNod, inNod;
    for (int i = 0; i < M; i++) {
        fin >> outNod >> inNod;
        noduri[outNod - 1].indexVecini.push_back(inNod - 1);
        noduri[inNod - 1].indexVecini.push_back(outNod - 1);
    }
}

void DFS() {
    while (!dfsStack.empty()) {
        int parent = dfsStack.top();
        dfsStack.pop();
        for(int nodNou : noduri[parent].indexVecini) {
            if (noduri[nodNou].vizitat) continue;
            noduri[nodNou].vizitat = true;
            noduri[nodNou].indexComponentConex = noduri[parent].indexComponentConex;
            dfsStack.push(nodNou);
        }
    }
}

int main() {
    citire();
    for (int i = 0; i < N; i++) {
        if (noduri[i].indexComponentConex != -1) continue;
        noduri[i].indexComponentConex = nrComponenteConexe;
        noduri[i].vizitat = true;
        nrComponenteConexe++;
        dfsStack.push(i);
        DFS();
    }
    fout << nrComponenteConexe;
    return 0;
}