Cod sursa(job #2427332)

Utilizator TeshyTesileanu Alexandru Teshy Data 31 mai 2019 16:29:23
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>

#include <fstream>

#include <vector>

#define Nmax 100009



using namespace std;



ifstream in("dfs.in");

ofstream out("dfs.out");

vector <int>graph[Nmax];

int viz[Nmax];



void DFS(int node)

{

    /// il vizitez

    viz[node] = 1;

    int lim = graph[node].size();

    for(int i = 0; i < lim; i++)

    {

        int vecin = graph[node][i];

        if(viz[vecin] == 0)

            DFS(vecin);

    }

}



int main()

{

    int N, M;

    in >> N >> M;

    int NrCompConexe = 0;

    int X, Y;

    for(int i = 0; i < M; i++)

    {

        in >> X >> Y;

        graph[X].push_back(Y);

        graph[Y].push_back(X);

    }

    for(int i = 1; i <= N; i++)

    {

        if(viz[i] == 0)

        {

            NrCompConexe ++;

            DFS(i);

        }

    }

    out << NrCompConexe;

    return 0;

}