Cod sursa(job #2781334)

Utilizator ionut31Ioan Ionescu ionut31 Data 9 octombrie 2021 10:19:19
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
//Parcurgere DFS - componente conexe

#include <iostream>
#include <fstream>
#include <vector>


using namespace std;

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

int n, m;
int vizitat[100001];

//liste de adiacente
vector<vector<int>> la;

void dfs(int x)
{
    vizitat[x] = 1;
    //fout << x << " ";
    for(int i=0; i<la[x].size(); ++i)
    {
        int y = la[x][i];
        if (vizitat[y] == 0)
            dfs(y);
    }
}

int main() {

    int conexe=0;
    fin>>n>>m;
    la.resize(n+1);
    for(int i=0; i<m; ++i)
    {
        int x ,y;
        fin >> x >> y;
        la[x].push_back(y);
        la[y].push_back(x);
    }

    for(int i=1; i<=n; ++i)
        if(vizitat[i]!=1)
        {
            conexe++;
            dfs(i);
        }
    fout<< conexe;

}