Cod sursa(job #3158111)

Utilizator HefaSteopoaie Vlad Hefa Data 17 octombrie 2023 19:06:43
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

void CreareLista(int n , int m, vector<vector<int>> &lista, bool orientat)
{
    for (int i = 0; i < m ; i ++)
    {
        int x, y;
        fin >> x >> y;
        if (x != y)
            lista[x].push_back(y);
        if (orientat == false)
            lista[y].push_back(x);
    }
}

void AfiseazaLista(vector<vector<int>> lista)
{
    for (int i = 1; i < lista.size(); i ++)
    {
        cout << i << ": ";
        for (int j = 0; j < lista[i].size(); j ++)
            cout << lista[i][j] << " ";
        cout << endl;
    }
}

void DFS(int n, int *marcat, vector<vector<int>> lista)
{
    marcat[n] = 1;
    for(int x : lista[n])
    {
        if (marcat[x] == 1)
            continue;
        marcat[x] = 1;
        DFS(x, marcat, lista);
    }
}

int main()
{
    int n, m;
    fin >> n >> m;
    vector<vector<int>> lista(n + 1);
    int marcat[n + 1];
    for (int i = 0; i <= n; i ++)
        marcat[i] = 0;
    
    CreareLista(n, m, lista, false);

    int componente = 0;
    
    for(int i = 1; i <= n; i ++)
    {
        if (marcat[i] == 0)
        {
            componente ++;
            DFS(i, marcat, lista);
        }
    }

    fout << componente;

    fin.close();
    fout.close();

    return 0;
}