Cod sursa(job #3335894)

Utilizator 10danutuCraciun Dan-Nicolae 10danutu Data 23 ianuarie 2026 20:05:06
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

ifstream f("dfs.in");

void dfs(int node, vector<vector<int>> &adj, vector<int> &vizitat)
{
    vizitat[node] = 1;
    for (auto vecin : adj[node])
    {
        if (!vizitat[vecin])
            dfs(vecin, adj, vizitat);
    }
}

int main()
{
    int m, n;

    f >> m >> n;
    int a, b;
    vector<vector<int>> adj(m + 1);
    while (f >> a >> b)
    {
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    vector<int> vizitat(m + 1, 0);

    int conexe = 0;
    for (int i = 1; i <= m; i++)
    {
        if (vizitat[i] == 0)
        {
            conexe++;
            dfs(i, adj, vizitat);
        }
    }
    cout << conexe;

    return 0;
}