Cod sursa(job #2783187)

Utilizator Andrei_SturzuAndrei Sturzu Andrei_Sturzu Data 13 octombrie 2021 22:29:28
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.06 kb
#include<iostream>
#include<queue>
#include<vector>
#include<fstream>
#include<queue>

using namespace std;

class Graph{
    private:
        int numberOfNodes = 0;
        int numberOfEdges = 0;
        vector<int> nodes;
        vector<vector<int>> neighbours;


    public:
        Graph(int n);
        Graph() {};
        int getNumberOfNodes() {return this->numberOfNodes;};
        void addDirectedEdge(int a, int b);
        void addUndirectedEdge(int a, int b);
        void bfs(int node);
        vector<int> bfs_cost(int node);
        void dfs(int node, vector<int> &visited);
        int NumberOfConnectedComponets();
};

Graph::Graph(int n){
    this->numberOfNodes = n;
    for(int i = 0; i <=n; i++)
        this->neighbours.push_back(vector<int>());
}

void Graph::addUndirectedEdge(int a, int b){
    this->neighbours[a].push_back(b);
    this->neighbours[b].push_back(a);
    this->numberOfEdges++;
}

void Graph::addDirectedEdge(int a, int b){
    this->neighbours[a].push_back(b);
    this->numberOfEdges++;
}

void Graph::bfs(int node){
    vector<int> visited(this->getNumberOfNodes() + 1);
    queue<int> q;

    q.push(node);
    visited[node] = 1;

    while(!q.empty()) {
        int currentNode = q.front();
        cout<<currentNode<<" ";
        q.pop();
        for(int i: this->neighbours[currentNode]) {
            if(!visited[i]) {
                q.push(i);
                visited[i] = 1;
            }
        }
    }
    cout<<"\n";
}

vector<int> Graph::bfs_cost(int node){
    vector<int> visited(this->getNumberOfNodes() + 1);
    queue<int> q;
    vector<int> cost(this->getNumberOfNodes() + 1);

    q.push(node);
    visited[node] = 1;

    while(!q.empty()) {
        int currentNode = q.front();
        q.pop();
        for(int i: this->neighbours[currentNode]) {
            if(!visited[i]) {
                q.push(i);
                cost[i] = cost[currentNode] + 1;
                visited[i] = 1;
            }
        }
    }

    for(int i = 1; i <= this->getNumberOfNodes(); i++){
        if(!visited[i])
            cost[i] = -1;
    }

    return cost;
}

void Graph::dfs(int node, vector<int> &visited) {
    visited[node] = 1;
    for(int i: this->neighbours[node])
        if(!visited[i])
            this->dfs(i, visited);

}

int Graph::NumberOfConnectedComponets() {
    vector<int> visited(this->getNumberOfNodes() + 1);
    int countConnected = 0;

    for(int i = 1; i <= this->getNumberOfNodes(); i++) {
        if(visited[i] == 0) {
            this->dfs(i, visited);
            countConnected++;
        }
    }

    return countConnected;
}

int main() {
    int n, m, startNode;

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

    fin >> n >> m;

    Graph graph = Graph(n);

    for(int i = 1; i <= m; i ++)
    {
        int a, b;
        fin >> a >> b;
        graph.addUndirectedEdge(a,b);
    }

    int result = graph.NumberOfConnectedComponets();
    cout<<result;
    fout<<result;

    return 0;
}