Cod sursa(job #3249775)

Utilizator razvanpackuPacurariu Razvan Mihai razvanpacku Data 17 octombrie 2024 19:38:14
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.44 kb
#include <iostream>
#include <list>
#include <stack>

#include <fstream>

using namespace std;

class Graph{
private:
    int nVert;
    int nEdg;
    bool oriented;
    list<int>* edges;

    void dfsUtil(int start, bool* visited){
        int current;
        stack<int> toVis;
        toVis.push(start);
        while(toVis.size()){
            current = toVis.top();
            toVis.pop();
            visited[current-1]=1;
            for(const auto& it : edges[current-1]){
                if(!visited[it-1]) toVis.push(it);
            }
        }
    }
public:
    Graph(int c_nVert, int c_nEdg, int c_oriented) : nVert(c_nVert), nEdg(c_nEdg), oriented(c_oriented){
        edges = new list<int>[nVert];
        int x,y;
        for(int i = 0 ; i<nEdg; i++){
            cin>>x>>y;
            edges[x-1].push_back(y);
            if(!oriented){
                edges[y-1].push_back(x);
            }
        }
    }
    Graph(int c_nVert, int c_nEdg, int c_oriented, istream& f) : nVert(c_nVert), nEdg(c_nEdg), oriented(c_oriented){
        edges = new list<int>[nVert];
        int x,y;
        for(int i = 0 ; i<nEdg; i++){
            f>>x>>y;
            edges[x-1].push_back(y);
            if(!oriented){
                edges[y-1].push_back(x);
            }
        }
    }
    bool existsEdge(int x, int y){
        for(const auto& it : edges[x-1]){
            if(it==y) return true;
        }
        return false;
    }
    void dfs(int start, ostream& g){
        bool* visited = new bool[nVert]{0};
        int current;
        stack<int> toVis;
        toVis.push(start);
        while(toVis.size()){
            current = toVis.top();
            toVis.pop();
            visited[current-1]=1;
            g<<current<<" ";
            for(const auto& it : edges[current-1]){
                if(!visited[it-1]) toVis.push(it);
            }
        }
        delete[] visited;
    }
    int nrConnected(){
        bool* visited = new bool[nVert]{0};
        int nr = 0;
        for(int i=0;i<nVert;i++){
            if(!visited[i]){
                nr++;
                dfsUtil(i+1, visited);
            }
        }
        delete[] visited;
        return nr;
    }
    ~Graph(){
        delete[] edges;
    }
};

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

int main()
{
    int n,m,o;
    f>>n>>m;
    Graph gr(n,m,0,f);
    g<<gr.nrConnected();
    return 0;
}