Cod sursa(job #2842869)

Utilizator elena284Rotaru Elena Alexia elena284 Data 1 februarie 2022 17:27:09
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 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 dfs(int nod1)
{
    viz[nod1]=1;
    nod *aux= new nod;
    aux=lista[nod1];
    while(aux!=NULL)
    {
        if(viz[aux->info]==0)
          dfs(aux->info);
        aux=aux->urm;
    }

}

int main()
{
    int m,x,y,nr=0;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        nod* aux=new nod;
        aux->info=y;
        aux->urm=lista[x];
        lista[x]=aux;
        aux=new nod;
        aux->info=x;
        aux->urm=lista[y];
        lista[y]=aux;
    }
    for(int i=1;i<=n;i++)
        if(viz[i]==0)
    {
        nr++;;
        dfs(i);
    }
    cout<<nr;

    return 0;
}