Cod sursa(job #2919056)

Utilizator utilizator20052022utilizatorr utilizator20052022 Data 14 august 2022 23:27:33
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;

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

class Graph{

private:

    int n_nodes;
    vector<bool> visited;
    vector<vector<int>> adj;
    int no_comp_conexe = 0;
public:
    Graph(){
        n_nodes = 0;
        adj = {};
    }

    Graph(int n, vector<vector<int>> &graph)
    {
        n_nodes = n;
        adj = graph;

        visited.resize(n+1, false);
    }

    void dfs(int root);

    void dfs_comp_conexe(int root);
    int comp_conexe();

};

void Graph::dfs(int root)
{
    visited[root] = true;
    for(int i = 0; i < adj[root].size(); ++i)
    {
        if(!visited[adj[root][i]]){
            dfs(adj[root][i]);
            cout<<adj[root][i]<<' ';
        }
    }

}

void Graph::dfs_comp_conexe(int root)
{
    visited[root] = true;
    for(int i = 0; i < adj[root].size(); ++i)
    {
        if(!visited[adj[root][i]]){
            dfs(adj[root][i]);
        }
    }
    no_comp_conexe++;
}

int Graph::comp_conexe()
{
    for(int i = 1; i <= n_nodes; ++i){
        if(!visited[i]) dfs_comp_conexe(i);
    }
    return no_comp_conexe;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, x, y;
    vector<vector<int>> a;
    fin>>n>>m;
    a.resize(n+1);

    for(int i = 0; i < m; ++i)
    {
        fin>>x>>y;
        a[x].push_back(y);
        a[y].push_back(x);
        //cout<<x<<' '<<y<<' ';
    }

    Graph g(n, a);
    fout<<g.comp_conexe();
    return 0;
}