Cod sursa(job #2822469)

Utilizator catarau.bianca.Bianca Catarau catarau.bianca. Data 23 decembrie 2021 23:44:55
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <bits/stdc++.h>
#define NMax 100001

using namespace std;

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

class graf
{
private:
    int n, m;
    bool vizitate[100001];
    vector <int> adj_list[100001];
public:
    graf(int n, int m);
    void citire_neorientat_adj_list();
    void DFS(int s);
    void conexe();
};
graf::graf(int n, int m)
{
    this->n = n;
    this->m = m;
}
void graf::citire_neorientat_adj_list()
{
    for(int i = 1; i <= m; ++i)
    {   int nod1, nod2;
        f>>nod1>>nod2;
        adj_list[nod1].push_back(nod2);
        adj_list[nod2].push_back(nod1);
    }
}
void graf::DFS(int start_node)
{
    vizitate[start_node] = 1;
    for(int i : adj_list[start_node])
        if(!vizitate[i])
            DFS(i);
}
void graf::conexe()
{
    int nr_comp = 0;
    for(int i = 1; i <= n; ++i)
        if(!vizitate[i])
            {
                nr_comp=nr_comp+1;;
                DFS(i);
            }
    g<< nr_comp;
}

int main()
{
    int n,m;
    f>>n>>m;
    graf G(n, m);
    G.citire_neorientat_adj_list();
    G.conexe();
    return 0;
}