Cod sursa(job #3121580)

Utilizator SorinBossuMarian Sorin SorinBossu Data 14 aprilie 2023 09:28:44
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>

using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
vector<int> adj[100011];
vector<int> v(100011, 0);
int main()
{
    int n, m;
    in >> n >> m;
    for ( int i = 1; i <= m; ++i )
    {
        int x, y;
        in >> x >> y;
        adj[x].emplace_back(y);
        adj[y].emplace_back(x);
    }

    int rez = 0;
    for ( int i = 1; i <= n; ++i )
        if ( v[i] == 0 )
        {
            rez++;
            stack<int> q;
            v[i] = 1;
            q.emplace(i);
            while ( !q.empty() )
            {
                auto nr = q.top();
                q.pop();
                for ( auto c:adj[nr] )
                   if ( v[c] == 0 )
                   {
                       v[c] = 1;
                       q.emplace(c);
                   }
            }
        }
        out << rez;
    return 0;
}