Cod sursa(job #2610039)

Utilizator dancu_mihai13Dancu Mihai dancu_mihai13 Data 4 mai 2020 01:18:56
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <bits/stdc++.h>

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

const int NMAX = 100005;
bool vizitat[NMAX] = {0};

void read(int &n, int &m, int mat[NMAX][NMAX])
{
    fin >> n >> m; int x, y;
    for(int i = 0; i < m; i++)
    {
        fin >> x >> y;
        mat[x][y] = 1;
        mat[y][x] = 1;
    }
}

void DFS(int n, int nod, int mat[NMAX][NMAX])
{
    vector <int> solutie;
    stack <int> stiva;
    solutie.reserve(n + 1);

    stiva.push(nod);
    solutie.push_back(nod);
    vizitat[nod] = 1;

    while(!stiva.empty())
    {
        int i = 1;
        while(i <= n && (vizitat[i] || !mat[i][stiva.top()]))
            i++;
        if(i <= n)
        {
            vizitat[i] = 1;
            solutie.push_back(i);
            stiva.push(i);
        }
        else
            stiva.pop();
    }
}

int main()
{
    int adiacent[NMAX][NMAX] = {0};
    int noduri, muchii, conexe = 0;

    read(noduri, muchii, adiacent);
    for(int i = 1; i <= noduri; i++)
        if(!vizitat[i])
        {
            DFS(noduri, i, adiacent);
            conexe++;
        }
    fout << conexe;
    return 0;
}