Cod sursa(job #2551465)

Utilizator NoodlesAndi Domnulete Noodles Data 19 februarie 2020 20:57:55
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream f("dfs.in");
ofstream f2("dfs.out");

int n, m, i;

int viz[20];

struct Nod{
    int info;
    Nod *next;

};

Nod listaDeAdiacenta[30];

void adaugare(Nod* prim, int y){
    Nod* newNode = new Nod;
    newNode->info = y;
    newNode->next = NULL;

    Nod* it = prim;
    while(it->next != NULL) {
        it = it->next;
    }

    it->next = newNode;
}

void dfs(int index_nod){

    if(viz[index_nod] == 1) {
        return;
    }

    viz[index_nod] = 1;


    Nod * cap = listaDeAdiacenta[index_nod].next;
    while(cap != NULL){
        dfs(cap -> info);
        cap = cap -> next;
    }

}

int main()
{
    int x, y;
    int index_node;

    f >> n >> m;

    for(i = 1; i <= m; i++)
    {
        f >> x >> y;

        Nod* listaX = &listaDeAdiacenta[x];
        adaugare(listaX, y);

        Nod* listaY = &listaDeAdiacenta[y];
        adaugare(listaY, x);
    }

    for(i = 1; i <= n; i++){
        viz[i] = 0;
    }

    int rez = 0;
    for(i = 1; i <= n; i++){
        if(viz[i] == 0){
            dfs(i);
            rez++;
        }
    }

    f2 << rez;
    return 0;
}