Cod sursa(job #2875445)

Utilizator Tudose_StefanTudose Alexandru Stefan Tudose_Stefan Data 21 martie 2022 17:34:07
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <fstream>
#include<vector>
#include <algorithm>
#include <set>

using namespace std;

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

int noduri, muchii, nod1, nod2, conexe;

void dfs(vector <set<int>> & vecini, vector <bool> & viz, int start)
{
    ///fout << "fac dfs pentru nodul " << start <<'\n';
    viz[start] = 1;
    for (auto i : vecini[start])
        if (viz[i] == 0)
            dfs(vecini, viz, i-1);
}


int main()
{
    fin >> noduri >> muchii;
    vector<set <int>> vecini;
    vecini.assign(noduri, {});
    vector <bool> viz;
    viz.assign(noduri, 0);
    while (muchii)
    {
        fin >> nod1 >> nod2;
        vecini[nod1-1].insert(nod2);
        vecini[nod2-1].insert(nod1);
        muchii--;
    }
    /*
    for (int j = 0; j < noduri; j++)
    {
        sort(vecini[j].begin(), vecini[j].end());
        if (vecini[j].size())
            for (auto i = vecini[j].end()-1; i> vecini[j].begin(); i--)
                if (*i == *(i-1))
                    vecini[j].erase(i);
    }*/
/*
    for (int j = 0; j < noduri; j++)
    {
        for (auto i : vecini[j])
            fout << i << ' ';
        fout << '\n';
    }
    */
    for (int j = 0; j < noduri; j++)
    {
        if (viz[j] == 0)
        {
            conexe++;
            dfs(vecini, viz, j);
        }
    }
    fout << conexe;
    return 0;
}