Cod sursa(job #2784595)

Utilizator AlexandraBoghiuAlexandra Boghiu AlexandraBoghiu Data 16 octombrie 2021 21:09:38
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.63 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
class Graph
{
private:
    int numberOfNodes, numberOfEdges;
    vector<vector<int>> listOfNeighbours;

public:
    Graph(int numberOfNodes = 0, int numberOfEdges = 0)
    {
        this->numberOfNodes = numberOfNodes;
        this->numberOfEdges = numberOfEdges;
    }
    ~Graph()
    {
        this->numberOfEdges = 0;
        this->numberOfNodes = 0;
    }
    void setNumberOfEdges(int);
    void setNumberOfNodes(int);
    void setEdges(int, int);
    int getNumberOfNodes();
    int getNumberOfEdges();
    void readEdges(istream &in);
    void printlistOfNeighbours(ostream &out);
    int numberOfConnectedComponents(bool[]);

private:
    void DFS(int node, bool[]);
};

void Graph::setNumberOfEdges(int m)
{
    numberOfEdges = m;
}
void Graph::setNumberOfNodes(int n)
{
    numberOfNodes = n;
}
void Graph::setEdges(int firstNode, int secondNode)
{
    listOfNeighbours[firstNode].push_back(secondNode);
}
int Graph::getNumberOfNodes()
{
    return numberOfNodes;
}
int Graph::getNumberOfEdges()
{
    return numberOfEdges;
}
void Graph::readEdges(istream &in)
{
    int firstNode, secondNode;
    listOfNeighbours.resize(numberOfNodes + 2);
    for (int i = 0; i < this->numberOfEdges; i++)
    {
        in >> firstNode >> secondNode;
        setEdges(firstNode, secondNode);
        setEdges(secondNode, firstNode);
    }
}
void Graph::printlistOfNeighbours(ostream &out)
{
    for (int i = 1; i < this->listOfNeighbours.size() - 1; i++)
    {
        out << i << ": ";
        for (int j = 0; j < listOfNeighbours[i].size(); j++)
            out << this->listOfNeighbours[i][j] << " ";
    }
}
void Graph::DFS(int node, bool visited[])
{
    // int visited[listOfNeighbours.size()];
    visited[node] = 1;
    //out<<node<<" ";
    for (int neighbour : listOfNeighbours[node])
    {
        //    out<<neighbour<<" ";
        if (!visited[neighbour])
            DFS(neighbour, visited);
    }
}
int Graph::numberOfConnectedComponents(bool visited[])
{
    int numberOfConnectedComponents = 0;
    for (int i = 1; i <= numberOfNodes; i++)
    {
        if (visited[i] == 0)
        {
            numberOfConnectedComponents++;
            DFS(i, visited);
        }
    }
    return numberOfConnectedComponents;
}
int main()
{
    int numberOfNodes, numberOfEdges;
    in >> numberOfNodes >> numberOfEdges;
    Graph Gr(numberOfNodes, numberOfEdges);
    Gr.readEdges(in);
    bool visited[numberOfNodes];
    out << Gr.numberOfConnectedComponents(visited);
    return 0;
}