Cod sursa(job #2659797)

Utilizator FLORENTIN-GIULIANO.DUMITRUDumitru Florentin Giuliano FLORENTIN-GIULIANO.DUMITRU Data 17 octombrie 2020 14:15:08
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <iostream>
#include <fstream>
#include <list>

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

struct pair{
    const int i,j;
    pair (int a, int b) : i(a), j(b){}
};

class Graf{
    std::list<int> * ad;
    bool *vis;
    int n;
    int nr;
    void DFS(int i);
public:
    Graf(int n);
    void addEdge(int i, int j);
    int DFS();
};

Graf :: Graf(int n){
    nr = 0;
    this -> n = n;
    vis = new bool[n+1];
    for (int i = 1; i <= n; i ++)
        vis[i] = false;
    ad = new std::list<int> [n+1];
}

void Graf::addEdge(int i, int j){
    ad[i].push_back(j);
    ad[j].push_back(i);
}

int Graf::DFS(){
    for (int i = 1; i <= n; i++)
    if (! vis[i]){
        nr ++;
        DFS(i);

    }
    return nr;
}

void Graf::DFS(int i){
    vis[i] = true;
    std::list<int> :: iterator j;
    for (j = ad[i].begin(); j != ad[i].end(); j ++)
    if (!vis[*j]){
        DFS(*j);
    }
}

int main()
{

    int n,m;
    in >> n >> m;

    Graf graf(n);

    while (m){

        int i, j;
        in >> i >> j;
        graf.addEdge(i,j);

        m --;
    }
   out << graf.DFS();

    out.close();
    in.close();
    return 0;
}