Cod sursa(job #3150885)

Utilizator andreandreAndreea Manole andreandre Data 18 septembrie 2023 21:40:56
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <vector>
#include <fstream>
using namespace std;

void dfs(int node, vector<vector<int>> &edges, vector<int> &parent) {
    for (auto &child : edges[node]) {
        if (parent[child] != -1) {
            parent[child] = node;
            dfs(child, edges, parent);
        }
    }
}
int main() {
    int N, M;
    ofstream fout("dfs.out");
    ifstream fin("dfs.in");
    fin >> N >> M;

    vector<vector<int>> edges(N, vector<int>(N, 0));
    vector<int> parent(N, -1);
    

    for (int i = 0; i < M; i++) {
        int x, y;
        fin >> x >> y;
        edges[x].push_back(y);
        edges[y].push_back(x);
    }
    
    int comp = 0;
    for (int i = 0; i < N; i++) {
        if (parent[i] == -1) {
            dfs(i, edges, parent);
            comp++;
        }
    }

    fout << comp;

    fin.close();
    fout.close();
    
    return 0;


}