Cod sursa(job #3158751)

Utilizator Steven23XHuma Stefan-Dorian Steven23X Data 19 octombrie 2023 18:48:22
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

std::ifstream f("dfs.in");
std::ofstream g("dfs.out");

const int MAX_N = 10e3;
std::vector<std::vector<int>> listaAdiacenta(MAX_N + 1);
int vis[MAX_N + 1];

// construire lista adiacenta
void buildListaAdiacenta(int n, int m)
{
    for (int i = 0; i <= n; ++i)
    {
        listaAdiacenta[i].clear();
    }

    for (int i = 0; i < m; i++)
    {
        int u, v;
        f >> u >> v;
        if (u != v)
            listaAdiacenta[u].push_back(v);
    }
}

// afisare lista adiacenta
void printListaAdiacenta(int n)
{
    for (int i = 1; i <= n; i++)
    {
        std::cout << i << ": ";
        for (int j = 0; j < listaAdiacenta[i].size(); j++)
        {
            std::cout << listaAdiacenta[i][j] << " ";
        }
        std::cout << "\n";
    }
}

// dfs

void DFS(int x)
{
    vis[x] = 1;
    for (auto next : listaAdiacenta[x])
    {
        if (!vis[next])
            DFS(next);
    }
}

int main()
{
    if (!f.is_open())
    {
        std::cerr << "Eroare deschidere fisier\n";
        return 1;
    }

    int n, m;
    f >> n >> m;
    buildListaAdiacenta(n, m);

    int nrComp = 0;
    for (int i = 1; i <= n; i++)
    {
        if (!vis[i])
            DFS(i), nrComp++;
    }

    g << nrComp;
    return 0;
}