Cod sursa(job #2427310)

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

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 >> A >> B;
        graph[A].push_back(B);
        graph[B].push_back(A);
    }
    for(int i = 1; i <= N; i++)
    {
        if(viz[i] == 0)
        {
            NrCompConexe ++;
            DFS(i);
        }
    }
    out << NrCompConexe;
    return 0;
}