Cod sursa(job #3270784)

Utilizator TeoRoGaming_YgVoinea Ionut-Florin TeoRoGaming_Yg Data 24 ianuarie 2025 14:22:44
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <fstream>
#include <vector>
using namespace std;

vector <int> v[100001];
bool verif[100001];

void dfs(int nod)
{
    verif[nod] = 1;
    for(auto y:v[nod])
    {
        if(!verif[y]) dfs(y); ///mergem recursiv prin nodurile nevizitate
    }
}

int main() ///parcurgere dfs cu aflarea numarului de componente conexe
{
    ifstream f("dfs.in");
    ofstream g("dfs.out");
    int N, M, X, Y, cnt = 0;
    f >> N >> M;
    for (int i = 1; i <= M; i++)
    {
        f >> X >> Y;
        v[X].push_back(Y);
        v[Y].push_back(X);
    }

    for (int i = 1; i <= N; i++)
    {
        if(!verif[i])
        {
            cnt++;
            dfs(i);
        }
    }
    g << cnt;
    return 0;
}