Cod sursa(job #3333786)

Utilizator cretu_elenaCretu Elena cretu_elena Data 15 ianuarie 2026 09:39:55
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>
#include <vector>
#define nmax 100001
using namespace std;
ifstream fin ("dfs.in");
ofstream fout ("dfs.out");
int n,nrc;
bool viz[nmax];


//vector<int> a; am declarat un vector din stl cu 0 elemente de tip int numit a
vector<int> a[nmax];//am declarat un vector cu nmax elemente de ti vector din stl cu 0 elemente de tip int numit a

void citire();
void afisare_lad();
void dfs(int x);

int main()
{
  int i;
    citire();
    for (i=1; i<=n; i++)
      if (viz[i]==0)
    {
      nrc++;
      dfs(i);
    }
    fout<<nrc;

    return 0;
}
void citire()
{
  int i,m,x,y;
  fin>>n>>m;
  for (i=0; i<m; i++)
  {
    fin>>x>>y;
    //adaug pe y la lista de adiacenta a lui x
    a[x].push_back(y);
    //doar pentru neprientate adaug si pe x in lista de adiacenta a lui x
    a[y].push_back(x);
  }
}
void afisare_lad()
{
  int i,j;
  for (i=1; i<=n; i++)
  {
    for (j=0; j<a[i].size(); j++)
      fout<<a[i][j]<<' ';
    fout<<'\n';
  }
}
void dfs(int x)
{
  int i;
  viz[x]=1;
  for (i=0; i<a[x].size(); i++)
    if (!viz[a[x][i]])
      dfs(a[x][i]);
}