Cod sursa(job #3216844)

Utilizator SabailaCalinSabaila Calin SabailaCalin Data 20 martie 2024 00:01:26
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.24 kb
#include <iostream>
#include <fstream>

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

template <typename T>
class vector
{
private:
    T **elem;
    int nrElem, cap;

    void resize();
public:
    vector();
    ~vector();

    void push_back(const T &element);

    const int &size();
    const int &capacity();

    T &operator[](const int idx);
};

template <typename T>
vector <T>::vector()
{
    this -> nrElem = 0;
    this -> cap = 1;
    this -> elem = new T*[1];
}

template <typename T>
vector <T>::~vector()
{
    for (int i = 0; i < this -> nrElem; i++)
    {
        delete this -> elem[i];
    }
    delete[] this -> elem;
}

template <typename T>
T &vector<T>::operator[](const int idx)
{
    if (idx < 0 || idx >= this -> nrElem)
        throw("This index is out of bounds");
    return *this -> elem[idx];
}

template <typename T>
void vector<T>::resize()
{
    this -> cap *= 2;
    T **temp = new T*[this -> cap];

    for (int i = 0; i < this -> nrElem; i++)
    {
        temp[i] = this -> elem[i];
    }
    delete[] this -> elem;

    this -> elem = temp;
}

template <typename T>
void vector<T>::push_back(const T &element)
{
    if (this -> nrElem == this -> cap)
        this -> resize();

    this -> elem[this -> nrElem] = new T(element);
    this -> nrElem++;
}

template <typename T>
const int &vector<T>::size()
{
    return this -> nrElem;
}

template <typename T>
const int &vector<T>::capacity()
{
    return this -> cap;
}

int n, m;
vector< int > Vertices[100001];
bool beenThere[100001];

inline void DFS(int Vertex)
{
    beenThere[Vertex] = true;
    for (int i = 0; i < Vertices[Vertex].size(); i++)
    {
        int neighbour = Vertices[Vertex][i];
        if (beenThere[neighbour] == false)
        {
            DFS(neighbour);
        }
    }
}

int main()
{
    int insule = 0;
    f >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        f >> x >> y;
        Vertices[x].push_back(y);
        Vertices[y].push_back(x);
    }
    for (int i = 1; i <= n; i++)
    {
        if (beenThere[i] == false)
        {
            insule++;
            DFS(i);
        }
    }
    g << insule;
}