Cod sursa(job #2818314)

Utilizator walentines44Serban Valentin walentines44 Data 15 decembrie 2021 20:36:32
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>

using namespace std;

struct Node{
    int value;
    Node* next;
};

void explore(Node* adj_list[], int x, bool visited[]){
    visited[x] = true;
    Node* temp = adj_list[x];
    while(temp != NULL){
        if(!visited[temp -> value]){
            explore(adj_list, temp -> value, visited);
        }
        temp = temp -> next;
    }
}

int DFS(Node* adj_list[], int N){
    bool visited[N] = {false};
    int cnt = 0;

    for(int i = 0; i < N; ++i){
        if(!visited[i]){
            cnt++;
            explore(adj_list, i, visited);
        }
    }

    return cnt;
}

void add(Node* &dest, int value){
    Node* p = new Node;
    p -> value = value;
    p -> next = dest;
    dest = p;
}

int main(){

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

    int N, M;
    fin >> N >> M;

    Node* adj_list[N] = {NULL};

    for(int i = 0; i < M; ++i){
        int x, y;
        fin >> x >> y;
        add(adj_list[x - 1], y - 1);
        add(adj_list[y - 1], x - 1);
    }

    int cnt = DFS(adj_list, N);
    fout << cnt << "\n";

    return 0;

}