Cod sursa(job #2879788)

Utilizator Tudose_StefanTudose Alexandru Stefan Tudose_Stefan Data 28 martie 2022 23:14:58
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 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;
bool viz[100001];


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


int main()
{
    fin >> noduri >> muchii;
    vector<set <int>> vecini;
    vecini.assign(noduri, {});
    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++)
    {
        fout << "Nodul " << j+1 << ": ";
        for (auto i : vecini[j])
            fout << i << ' ';
        fout << '\n';
    }*/
    for (int j = 0; j < noduri; j++)
    {
        if (viz[j] == 0)
        {
            conexe++;
            viz[j] = 1;
            dfs(vecini, viz, j);
        }
    }
    fout << conexe;
    return 0;
}