Cod sursa(job #2853913)

Utilizator MariusAndrei16Pricope Marius MariusAndrei16 Data 20 februarie 2022 18:40:00
Problema Parcurgere DFS - componente conexe Scor 45
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int mAdiacenta[1000][1000];
int vizitat[1000];
int N, M; //N - numarul de noduri M - numarul de muchii

bool Parcurs(int freq[], int noduri)
{
    for (int i = 1; i <= noduri; i++)
        if(freq[i] == 0)
            return false;
    return true;
}

void DFS(int nod, int noduri)
{
    vizitat[nod] = 1;
    for (int i = 1; i <= noduri; i++)
    {
        if(vizitat[i] == 0 && mAdiacenta[nod][i] == 1)
        {
            vizitat[i] = 1;
            DFS(i,noduri);
        }
    }
    
}


int main()
{
    in >> N >> M;
    int x, y;
    for (int i = 0; i < M; i++)
    {
        in >> x >> y;
        mAdiacenta[x][y] = 1;
        mAdiacenta[y][x] = 1;
    }

    int conexe = 0;

    for (int i = 1; i <= N; i++)
    {
        if(vizitat[i] == 0)
        {
            DFS(i,N);
            conexe++;
        }
    }
    
    out << conexe;

    return 0;
}