Cod sursa(job #2785312)

Utilizator StefaniaCriStefania Cristea StefaniaCri Data 18 octombrie 2021 15:02:40
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.68 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;
int n,m;
#define Nmax 100001
vector <int> la[Nmax];
int visited[Nmax];
int nr_conex = 0;
void dfs(int start)
{
  visited[start] = nr_conex;
  for(auto i:la[start])
  {
      if(!visited[i])
        dfs(i);
  }
}
int main()
{   ifstream f ("dfs.in");
    ofstream g("dfs.out");
    f>>n>>m;
    for (int i=0;i<m;i++)
    {
        int x,y;
        f>>x>>y;
        la[x].push_back(y);
        la[y].push_back(x);
    }

    for(int i=1;i<=n;i++)
        if(!visited[i])
         {   nr_conex++;
             dfs(i);
         }
    g<<nr_conex;
    return 0;
}