Cod sursa(job #3361281)

Utilizator RaresPanuPanu Rares RaresPanu Data 22 iulie 2026 19:07:40
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include <fstream>
#include <vector>

using namespace std;

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

void dfs(vector<vector<int>> &graph, int start, vector <int> &viz) {
    viz[start]=1;
    for (int i=0; i<graph[start].size(); i++) {
        if (viz[graph[start][i]] == 0) {
            dfs(graph, graph[start][i], viz);
        }
    }
}


int main() {
    int n,m;
    fin >> n >> m;

    vector <vector<int>> graph(n+1);

    for (int i=1;i<=m;i++) {
        int a,b;
        fin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    vector <int> viz(n+1);
    int cnt=0;
    for (int i=1;i<=n;i++) {
        if (viz[i]==0) {
            dfs(graph, i, viz);
            cnt++;
        }
    }
    fout << cnt;
    return 0;
}