Cod sursa(job #3161837)

Utilizator Alex_DumitrascuAlex Dumitrascu Alex_Dumitrascu Data 28 octombrie 2023 09:19:46
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.68 kb
#include <iostream>
#include <vector>
using namespace std;
vector <int> g[100005];
bool vizited[100005];
void dfs (int nod)
{
    vizited[nod]=1;
    for (int i=0; i<g[nod].size(); i++) {
        int vecin=g[nod][i];
        if (!vizited[vecin]) dfs(vecin);
    }
}
int main()
{
    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);
    int n, m, a, b;
    int conexe=0;
    cin>>n>>m;
    for (int i=1; i<=m; i++) {
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for (int i=1; i<=n; i++) {
        if (!vizited[i]) {
            conexe++;
            dfs(i);
        }
    }
    cout<<conexe;
    return 0;
}