Cod sursa(job #3254545)

Utilizator ioana3000ioana profir ioana3000 Data 7 noiembrie 2024 19:39:17
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <iostream>
#include <vector>
#include <fstream>
#define NMAX 100005
using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");

int n, nrc;
 vector <int> A[NMAX];
///a[ x] va fi un vec din stl care retie lista de adacenta a lui x
 ///d[x] gradul lui x/grd exterior

int viz[NMAX]; /// viz[x] = nr daca a fost vizitat in comp conexa cu num nr
void citire();
void dfs(int x);
void afisare();
int main()
{
    ///graf rep prin liste de adiacenta tipul vector din biblioteca stl
    citire();
    int i;
    for(i = 1 ; i <= n; i++)
        if(!viz[i])
        {
            nrc ++;
            dfs(i);
        }
    afisare();
    return 0;
}
void citire()
{
    int  i, x, y, m;
    fin >> n >> m;
    while(fin >> x >> y)
    {
        ///varful y e adaugat la lista de adiacenta a lui x
        A[x].push_back(y);
        /// varful x e adaugat la lista de adiacenta a lui x
        A[y].push_back(x);
    }
}
void dfs(int x)
{
    int i;
    viz[x] = nrc;
    ///parcurg vecinii varfului x sau adiacente
    for(i = 0; i < A[x].size(); i++)
        if(!viz[A[x][i]])
            dfs(A[x][i]);
}
void afisare()
{
    fout << nrc << '\n';
    /*int i, j;
    for(i = 1; i <= nrc; i++)
    {
        for(j = 1; j <= n; j ++)
            if(viz[j] == i)
                fout << j << ' ';
        fout << '\n';
    }*/

}