Cod sursa(job #3364791)

Utilizator iulia_toderica16Iulia Toderica iulia_toderica16 Data 11 septembrie 2026 16:31:54
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>
#include <fstream>
#include <map>
#include <vector>

using namespace std;

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

map <int, vector<int>> lista;
bool used[101];
vector <vector<int>> connected;

void dfs(int k, vector<int>&component)
{
    used[k]=true;
    component.push_back(k);
    for(auto i : lista[k])
    {
        if(used[i]==false)
            dfs(i, component);
    }
}

int main()
{
    int n, m;
    int a, b;
    fin>>n>>m;

    for(int i=1; i<=m; i++)
    {
        fin>>a>>b;
        lista[a].push_back(b);
        lista[b].push_back(a);
    }

    for(int i=1; i<=n; i++)
    {
        if(used[i]==false)
        {
            vector<int>component;
            dfs(i, component);
            connected.push_back(component);
        }
    }

    fout<<connected.size();

    return 0;
}