Cod sursa(job #2788242)

Utilizator faalaviaFlavia Podariu faalavia Data 25 octombrie 2021 13:03:27
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.61 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
//#include "Graph.h"
//#include "DirectedGraph.h"
//#include "UndirectedGraph.h"
using namespace std;


class Graph {
    int nrNodes; //number of nodes
    vector<vector<int>> edges; // list of connections between nodes
public:
    Graph(int _nrNodes);
    int getNrNodes() const;
    void setEdge(int node, int neighbour);
    int nrConnectedComponents();
    void printEdges();
    ~Graph();
private:
    void DFS(int, vector<int>&);
};

Graph::Graph(int _nrNodes)
{
    this -> nrNodes = _nrNodes;
    this -> edges.resize(this -> nrNodes + 1, vector<int>());
    /*
     * Nodes start from 1, but index starts at 0
     */
}

int Graph::getNrNodes() const
{
    return this -> nrNodes;
}

int Graph::nrConnectedComponents()
{
    int ans = 0;
    vector<int>visited(this -> nrNodes+1, 0);
    for(int i = 1 ; i <= this -> nrNodes; ++i)
        if(visited[i] == 0)
        {
            DFS(i, visited);
            ++ans;
        }
    return ans;
}
void Graph::DFS(int start, vector<int>& visited)
{
    visited[start] = 1;
    for(int i = 0; i < edges[start].size(); ++i)
    {
        int neighbour = edges[start][i];
        if(visited[neighbour] == 0)
        {
            visited[neighbour] = 1;
            DFS(neighbour, visited);
        }
    }
}

Graph::~Graph()
{
    this -> nrNodes = 0;
    for(int i = 1; i <= edges.size(); ++i)
        this -> edges[i].clear();
}

void Graph::printEdges()
{
  for(int i = 1; i < edges.size(); i++)
  {
      cout << i<< ": ";
      for(auto it: edges[i])
          cout << it<< " ";
      cout << "\n";
  }
}

void Graph::setEdge(int node, int neighbour)
{
   this ->edges[node].push_back(neighbour);
}


//------------------------------------------------------------------------------------------

class UndirectedGraph: public Graph{

public:
    UndirectedGraph(int _nrNodes);
    void addEdge(int node, int neighbour);
    ~UndirectedGraph();
};


UndirectedGraph::UndirectedGraph(int _nrNodes): Graph(_nrNodes){}

void UndirectedGraph::addEdge(int node, int neighbour)
{
    this -> setEdge(node, neighbour);
    this -> setEdge(neighbour, node);
}

UndirectedGraph::~UndirectedGraph() {}

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

    int n, m, x, y;
    fin >> n >> m;

    UndirectedGraph *ug = new UndirectedGraph(n);
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y;
        ug -> addEdge(x, y);
    }

    fout << ug -> nrConnectedComponents();
    return 0;

}