Cod sursa(job #2681456)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 5 decembrie 2020 15:27:00
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

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

vector <int> G[100005];
bool vizitat[100005];

void dfs(int curent)
{
    if(vizitat[curent])
    {
        return;
    }
    vizitat[curent]=1;
    for(int i=0; i<G[curent].size(); i++)
    {
        int vecin=G[curent][i];
        if(!vizitat[vecin])
        {
            dfs(vecin);
        }
    }
}
int main()
{
    int nr_noduri, nr_muchii;
    int c=0;
    fin>>nr_noduri>>nr_muchii;
    for(int i=0; i<nr_muchii; i++)
    {
        int nod1, nod2;
        fin>>nod1>>nod2;
        nod1--;
        nod2--;
        G[nod1].push_back(nod2);
        G[nod2].push_back(nod1);
    }
    for(int i=0; i<nr_noduri; i++)
    {
        if(!vizitat[i])
        {
            dfs(i);
            c++;
        }
    }
    fout<<c;
    return 0;
}