Cod sursa(job #2666716)

Utilizator anamaria2602Avram Ana Maria anamaria2602 Data 2 noiembrie 2020 14:05:08
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <fstream>
#include <vector>
using namespace std;

ifstream cin("dfs.in");
ofstream cout("dfs.out");

vector <int> M[100001];
int Viz[100001], X1, X2;
int NrComponenteConexe, Dimensiune, N1, N2;
void Dfs ( int x )
{
    if ( Viz[x] == 0 )
    {
        Viz[x] = 1; ///vizitam nodul curent
        Dimensiune = M[x].size(); ///aflam dimensiunea
        for ( int i = 0; i < M[x].size(); i ++ ) ///parcurgem vectorul de muchii al nodului
            if ( Viz[ M[x][i] ] == 0 ) ///daca am gasit o muchie care nu a fost vizitata
                Dfs ( M[x][i] ); ///apelam recursiv
    }
}
int main()
{
    cin >> N1 >> N2;
    for ( int i = 1; i <= N2; i ++ )
    {
        ///adaugam nodurile, pe rand, in lista de muchii a celuilalt
        cin >> X1 >> X2;
        M[X1].push_back(X2);
        M[X2].push_back(X1);
    }
    for ( int i = 1; i <= N1; i ++)
        if ( Viz[i] == 0 ) ///daca nodul n-a fost vizitat
        {
            NrComponenteConexe++; ///actualizam nr de componente conexe
            Dfs(i);
        }
    cout << NrComponenteConexe;
    return 0;
}