Cod sursa(job #2919302)

Utilizator utilizator20052022utilizatorr utilizator20052022 Data 16 august 2022 17:35:54
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.27 kb
#include <iostream>
#include<fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

class Graph{
private:
    int n_nodes;
    vector<vector<int>> adj;
    vector<pair< int , pair<int,int>> > adj_weight;
public:
    Graph(){
        n_nodes = 0;
        adj = {};
    }
    Graph(int n, vector<vector<int>> &gr){
        n_nodes = n;
        adj = gr;
    }

    void dfs(int node, vector<bool> &visited, vector<vector<int>> &gr);
    void dfs_sort_top(int node, vector<bool> &visited, vector<vector<int>> &gr, vector<int> &solution);
    void dfs_comp_conexe(int node, vector<bool> &visited, vector<vector<int>> &gr, int &cnt);
    void solve_sort_top();
    void solve_comp_conexe();
};

void Graph:: dfs(int node, vector<bool> &visited, vector<vector<int>> &gr){
    visited[node] = true;
    for(auto &x: gr[node]){
        if(!visited[x]) dfs(x, visited, gr);
    }
}

void Graph:: dfs_comp_conexe(int node, vector<bool> &visited, vector<vector<int>> &gr, int &cnt){
    visited[node] = true;
    for(auto &x: gr[node]){
        if(!visited[x]) dfs(x, visited, gr);
    }
    cnt++;
}

void Graph:: dfs_sort_top(int node, vector<bool> &visited, vector<vector<int>> &gr, vector<int> &solution){
    visited[node] = true;
    for(auto &x: gr[node]){
        if(!visited[x]) dfs_sort_top(x, visited, gr, solution);
    }
    solution.push_back(node);
}

void Graph::solve_sort_top(){
    vector<bool> v(n_nodes+1, false);
    vector<int> sol(n_nodes+1);

    for(int i = 1; i <= n_nodes; ++i){
        if(!v[i]) dfs_sort_top(i, v, adj, sol);
    }
    reverse(sol.begin(), sol.end());
    for(int i = 0; i < n_nodes; ++i)
        //cout<<sol[i]<<' ';
        fout<<sol[i]<<' ';
}

void Graph::solve_comp_conexe(){
    vector<bool> v(n_nodes+1, false);
    vector<int> sol(n_nodes+1);
    int ans = 0;

    for(int i = 1; i <= n_nodes; ++i){
        if(!v[i]) dfs_comp_conexe(i, v, adj, ans);
    }

    fout<<ans<<' ';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, x, y;
   // cin>>n>>m;
    fin>>n>>m;
    vector<vector<int>> aux(n+1);
    for(int i = 0; i < m; ++i){
       // cin>>x>>y;
        fin>>x>>y;
        aux[x].push_back(y);
    }

    Graph g = Graph(n, aux);
    g.solve_comp_conexe();
    return 0;
}