Cod sursa(job #2558301)

Utilizator richardionelRichard Ionel richardionel Data 26 februarie 2020 14:28:48
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

const int Nlimita = 100001;
unsigned int N ,M ,componente = 0;
vector <int> muchii[Nlimita];
int vizitat[Nlimita];

void dfs(int nodcurent)
{
    vizitat[nodcurent] = 1;
    for (unsigned int i = 0 ;i < muchii[nodcurent].size() ;i++)
    {
        int vecin = muchii[nodcurent][i];
        if (! vizitat[vecin])
            dfs(vecin);
    }
}

void read()
{
   fin >> N >> M;
   for (unsigned int i = 1 ;i <= M ;i++)
   {
       int x ,y;
       fin >> x >> y;
       muchii[x].push_back(y);
       muchii[y].push_back(x);
   }
   for (unsigned int i = 1 ;i <= N ;i++)
   {
       if (vizitat[i] == 0){
            componente++;
            dfs(i);}
   }
}




int main()
{
    read();
    fout << componente;
}