Cod sursa(job #2926629)

Utilizator IonescuRalucaIonescu Andreea Raluca IonescuRaluca Data 18 octombrie 2022 11:12:29
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

ifstream f("dfs.in");
ofstream g("dfs.out");
int noduri,muchii,i;
int nr;
vector< int > vizitate(100001,0);
int compConexe[100001]={0};
vector< vector<int> > ListaAdiacenta()
{   int x,y;
    vector< vector<int> > lista(noduri+1);

    for( i=0;i<muchii;i++)
    {
        f>>x>>y;
        lista[x].push_back(y);
        lista[y].push_back(x);
    }
    return lista;
}
//void afisareListaAdiacenta(vector<vector<int>> &lista)
//{
//    for(size_t x=1; x< lista.size();x++)
//    {
//        cout<<x<<": ";
//        for(auto y:lista[x])
//            cout<<y<<" , ";
//        cout<<endl;
//    }
//    cout<<endl;
//}
void DFS(int nod,vector< vector<int> > &lista,int componenteConexe[10001])
{
    vizitate[nod]=1;
    componenteConexe[nod]=nr;
//    for(int i = 0; i < lista[nod].size(); i++)
//        if(!vizitate[lista[nod][i]])
//            DFS(lista[nod][i],lista,componenteConexe);


    for(auto y:lista[nod])
           if(!vizitate[y])
               DFS(y,lista,componenteConexe);

}

int gasesteCompConexe(vector< vector<int> > &lista,int N,int componenteConexe[10001])
{
    for(int i=1;i<=N;i++)
        if(!vizitate[i])
        {
            nr++;
            DFS(i,lista,componenteConexe);
        }
    return nr;
}


int main()
{
    f>>noduri>>muchii;
    auto listaAdiacenta= ListaAdiacenta();
//    afisareListaAdiacenta(listaAdiacenta);

    g<<gasesteCompConexe(listaAdiacenta,noduri,compConexe);



    return 0;
}