Cod sursa(job #2610049)

Utilizator dancu_mihai13Dancu Mihai dancu_mihai13 Data 4 mai 2020 02:01:27
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <bits/stdc++.h>

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

const int NMAX = 100005;
bool vizitat[NMAX] = {0};
vector <int> adiacent[NMAX];
int noduri;

void read(int &m)
{
    fin >> noduri >> m; int x, y;
    for(int i = 0; i < m; i++)
    {
        fin >> x >> y;
        adiacent[x].push_back(y);
        adiacent[y].push_back(x);
    }
}

void DFS(int nod)
{
    vizitat[nod] = 1;
    for(unsigned int i = 0; i < adiacent[nod].size(); i++)
    {
        int vecin = adiacent[nod][i];
        if(!vizitat[vecin])
            DFS(vecin);
    }
}

int main()
{
    int muchii, conexe = 0;

    read(muchii);
    for(int i = 1; i <= noduri; i++)
        if(!vizitat[i])
        {
            DFS(i);
            conexe++;
        }
    fout << conexe;
    return 0;
}