Cod sursa(job #2842861)

Utilizator mitumitucristinaMitu Cristina mitumitucristina Data 1 februarie 2022 17:10:34
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>
using namespace std;
ifstream cin("dfs.in");
ofstream cout("dfs.out");
int n;
struct nod
{
    int info;
    nod* urm;
};
nod* lista[100001];

int viz[100001];

void citire_graf()
{
    int m, n1,n2;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>n1>>n2;
        nod* aux=new nod;
        aux->info=n2;
        aux->urm=lista[n1];
        lista[n1]=aux;
        aux=new nod;
        aux->info=n1;
        aux->urm=lista[n2];
        lista[n2]=aux;
    }
}
int nrn;

void dfs(int nodd)
{
    viz[nodd]=1;
    nrn++;
    nod*aux=new nod;
    aux=lista[nodd];
    while(aux!=NULL)
    {
        if(viz[aux->info]==0)
            dfs(aux->info);
        aux=aux->urm;
    }
}
int main()
{
    int nr=0;
    citire_graf();
    for(int i=1;i<=n;i++)
        if(viz[i]==0){
            dfs(i);
            nr++;
        }
    cout<<nr;
        return 0;
}