Cod sursa(job #2427313)

Utilizator teoschipor00Teodora Schipor teoschipor00 Data 31 mai 2019 16:00:52
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <fstream>
#include <vector>
#define Nmax 100003

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;
}