Cod sursa(job #3272309)

Utilizator BogdancxTrifan Bogdan Bogdancx Data 29 ianuarie 2025 09:15:58
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

vector<int> visited;

void dfs(const vector<vector<int>>& graph, int n, int start)
{
    stack<int> s;

    s.push(start);
    visited[start] = true;
    
    while(!s.empty())
    {
        int node = s.top();
        s.pop();
        
        for(int neigh: graph[node])
        {
            if(!visited[neigh])
            {
                visited[neigh] = true;
                s.push(neigh);
            }
        }
    }
}

int main()
{
    ifstream fin("dfs.in");
    ofstream fout("dfs.out");
    
    int n, m, k;
    
    fin >> n >> m;

    visited.resize(n + 1, false);
    vector<vector<int>> graph(n + 1);
    
    for(int i = 0; i < m; i++) {
        int a, b;
        fin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    
    int cnt = 0;

    for(int i = 1; i <= n; i++) {
        if(!visited[i]) {
            dfs(graph, n, i);
            cnt++;
        }
    }

    fout << cnt << endl;

    return 0;
}