Cod sursa(job #3345874)

Utilizator razvanantonAnton Razvan-Stefan razvananton Data 11 martie 2026 16:54:25
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

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

const int maxSz=100005;

bool visited[maxSz];

vector<int> adj[maxSz];

int main()
{
    int n,m;
    fin>>n>>m;
    stack<int> s;
    int count=0;
    int x,y,node;
    for(int i=0;i<m;++i)
    {
        fin>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    for(int i=1;i<=n;++i)
    {
        if(!visited[i])
        {
            ++count;
            s.push(i);
            visited[i]=1;
            while(!s.empty())
            {
                node=s.top();
                s.pop();
                for(auto el : adj[node])
                {
                    if(!visited[el])
                    {
                        s.push(el);
                        visited[el]=1;
                    }
                }
            }
        }
    }
    fout<<count;


    return 0;
}