Cod sursa(job #2787315)

Utilizator gabrielanideleaNidelea Gabriela-Andreea gabrielanidelea Data 22 octombrie 2021 22:32:31
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include<iostream>
#include<fstream>
#include<queue>
#include<vector>

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

class graf{
public:
    //bfs - declarari
    //int N, M, S, vizitat[100010], minime[100010];
    //vector<int> stocare[100010];
    //queue<pair<int, int>> coada;

    //dfs - declarari
    int N, M;
    vector<int>ok; //pt a marca nodul ca vizitat sau nu - 0 sau 1
    vector<vector<int>>D;
    graf(){}



    //DFS
    void dfs(int start)
    {
        ok[start] = 1;
        for(auto i: D[start]) // parcurg D
            if(!ok[i])
            {
                ok[i] =1;
                dfs(i);
            }


    }
    void creare_graf_Dfs(int N, int M)
    {
        this-> N = N;
        this -> M =M;
        D=vector<vector<int>>(N+1);
        ok=vector<int>(N+1);

    }
    void creare_adiacente_Dfs(int M)
    {
         int nod1, nod2;
         for(int i = 1; i<= M; i++)
        {
            f>>nod1>>nod2;
            D[nod1].push_back(nod2);
            D[nod2].push_back(nod2);
        }

    }

};
graf Gr;
int main()
{


    //DFS
    int N, M, k;
    f>>N>>M;
    Gr.creare_graf_Dfs(N, M);
    Gr.creare_adiacente_Dfs(M);
    for(int i =1; i<= N; i++)
            if(!Gr.ok[i])
            {
                k++;
                Gr.dfs(i);
            }
    g<<k<<" ";
    return 0;

}