Cod sursa(job #2927577)

Utilizator elenaa_g23Elena Georgescu elenaa_g23 Data 20 octombrie 2022 21:20:53
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include<iostream>
#include<fstream>
#include<stack>
#include<vector>
#define MAX 100005

using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");

int n,m,comp_con=0;
stack<int> stiva;
int vizitat[MAX];
vector<vector<int>> lista_adiacenta;

void lista_construire(){
    int i,j,k;
    for(i=0;i<m;i++){
        f>>j>>k;
        lista_adiacenta[j].push_back(k);
    }
}

void lista_afisare(){
    int i,j;
    for(i=1;i<=n;i++){
        cout<<i<<": ";
        for(j=0;j<lista_adiacenta[i].size();j++)
            cout<<lista_adiacenta[i][j]<<' ';
        cout<<endl;
    }
}

void dfs()
{
    int i,j;
    i=1;
    while(i<=n)
    {
        if(vizitat[i]==1) i++;

        else
            {
        vizitat[i]=1;
        stiva.push(i);
        while(!stiva.empty())
        {
            stiva.pop();
            for(j=0;j<lista_adiacenta[i].size();j++)
            {
                if(vizitat[lista_adiacenta[i][j]]==0)
                {stiva.push(lista_adiacenta[i][j]);
                 vizitat[lista_adiacenta[i][j]]=1;}
            }
        }
        comp_con++;

        i++;
    }
    }

    g<<comp_con;
}


int main()
{
    f>>n>>m;
    lista_adiacenta.resize(n+1);
    lista_construire();
    for(int i=1;i<=n;i++)
        vizitat[i]=0;
    dfs();
}