Cod sursa(job #2672534)

Utilizator MateGMGozner Mate MateGM Data 14 noiembrie 2020 10:28:08
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

void dfs(int start,int n,vector<bool>&ell,const vector<vector<int> >&adj)
{
    ell[start]=true;
    for(int sz:adj[start]){
        if(!(ell[sz]))
           dfs(sz,n,ell,adj);
    }
}

int main()
{
    ifstream be("dfs.in");
    ofstream ki("dfs.out");
    int n,m;
    be>>n>>m;
    vector<vector<int> >adj(n+1);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        be>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    vector<bool>ell(n+1,false);
    int db=0;
    for(int i=1;i<=n;i++)
        if(ell[i]==false)
        {
            db++;
            dfs(i,n,ell,adj);
        }
    ki<<db;
    return 0;
}