Cod sursa(job #3351099)

Utilizator Andrei1209Andrei Mircea Andrei1209 Data 16 aprilie 2026 18:50:15
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

const int Nmax = 1e5 + 5;
vector <int> vecini[Nmax];
int n, viz[Nmax];
void dfs( int sursa )
{
    queue<int> coada;
    coada.push(sursa);
    while ( !coada.empty() )
    {
        int fr = coada.front();
        coada.pop();
        viz[fr] = 1;

        for ( int i = 0; i < vecini[fr].size(); ++i )
        {
            if ( viz[  vecini[fr][i]  ] == 0 )
            {
                coada.push(vecini[fr][i]);
            }
        }
    }
}
int main()
{
    int i, m, sursa;
    fin >> n >> m;
    for ( i = 1; i <= m; ++i )
    {
        int a, b;
        fin >> a >> b;
        vecini[a].push_back(b);
        vecini[b].push_back(a);
    }
    int sol = 0;
    for ( i = 1; i <= n; ++i )
    {
        if ( viz[i] == 0 )
        {
            ++sol;
            dfs(i);
        }
    }
    fout << sol;
    return 0;
}