Cod sursa(job #2788643)

Utilizator dariarunceanuRunceanu Daria dariarunceanu Data 26 octombrie 2021 10:35:11
Problema Parcurgere DFS - componente conexe Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <fstream>
#include<list>
#include<vector>
#include<queue>

using namespace std;

int tata[100];

void citireGraf(int &N, int &M, vector<list<int> > &L, const char *filename)
{
    ifstream fin(filename);
    int x,y;
    fin >> N >> M;
    L.resize(N+1);
    for (int i=1; i<=M; i++)
    {
        fin >> x >> y;
        L[x].push_back(y);
        L[y].push_back(x);
    }
    fin.close();
}

void afisare(vector<list<int> > &L)
{
    for(int i = 1; i<L.size();i++)
    {
        cout << i << ":";
        for(int j:L[i])
            cout << j << " ";
        cout << "\n";
    }
}

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

    for(int i : L[nod])
    {
        if(viz[i] == 0)
        {
            tata[i] = nod;
            dfs(i,L,viz);
        }
    }
        
}


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

}