Cod sursa(job #2788619)

Utilizator robbie112Popescu Stefan robbie112 Data 26 octombrie 2021 08:43:08
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>
#include <fstream>
#include<list>
#include<vector>
using namespace std;
void citireGraf(int &N, int &M, vector<list<int> > &L, const char *filename)
{
    ifstream fin(filename);

    fin >> N >> M;
    L.resize(N+1);
    int x, y;
    for (int i=0;i<M;++i)
    {
        fin >> x >> y;
        L[x].push_back(y);
        L[y].push_back(x);
    }

    fin.close();
}
void dfs(int nod, vector<list<int>> &L, vector<int> &viz)
{
    viz[nod] = 1;

    for(int x : L[nod]) // pentru fiecare nod x in lista de vecini
    {
        if(viz[x] == 0)
        {
            dfs(x, L, viz);
        }
    }

}
int main() 
{
    int N,M;
    vector<list<int> > L;
    citireGraf(N,M,L,"dfs.in");
    vector<int>viz(N+1,0);
    int compConexe=0;
    for(int i=1;i<=N;++i)
    {
        if(viz[i]==0){dfs(i, L, viz); compConexe++;}
    }
    
    ofstream fout("dfs.out");
    fout << compConexe;
    fout.close();

    return 0;
}