Cod sursa(job #2719057)

Utilizator sebastian.barbarasaSebastian Barbarasa sebastian.barbarasa Data 9 martie 2021 15:40:27
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.71 kb
#include <fstream>
#include <vector>
#define NMAX 100002
using namespace std;

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

vector <int> G[NMAX]; ///G[i] lista de adiacenta a varfului i
bool viz[NMAX];
int n, nr;

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

int main()
{int i;
 citire();
 for (i=1; i<=n; i++)
      if (!viz[i])
          dfs(i), nr++;
 fout<<nr<<'\n';
 fin.close();
 fout.close();
 return 0;
}

void dfs(int x)
{int i;
 viz[x]=1;
 for (i=0; i<G[x].size(); i++)
      if (!viz[G[x][i]])
          dfs(G[x][i]);
}

void citire()
{
 int k, m, i, j;
 fin>>n>>m;
 for (k=0; k<m; k++)
     {
      fin>>i>>j;
      G[i].push_back(j);
      G[j].push_back(i);
     }
}