Cod sursa(job #2795631)

Utilizator Teodora11faranume Teodora11 Data 6 noiembrie 2021 18:36:16
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.95 kb
#include <fstream>
#include <queue>
#include <stack>
#include <vector>

using namespace std;

class Algorithms
{
public:
    static void DFS( const vector<vector<int>>& adjacencyList, int startNode, vector<bool>& visited )
    {
        stack<int> nodes;
        nodes.push( startNode );  // adaugam nodul de start in stiva
        //vector<int> traversal;    // vectorul in care retinem parcurgerea

        while( !nodes.empty() ) {
            // scoatem varful stivei
            int crtNode = nodes.top();
            nodes.pop();

            if( visited[crtNode] )  // se poate sa fi vizitat deja nodul (un nod poate aparea de 2 ori in stiva)
                continue;

            visited[crtNode] = true;         // vizitam nodul
            //traversal.push_back( crtNode );  // adaugam nodul la parcurgere
            // bagam vecinii nevizitati in stiva
            for( auto node : adjacencyList[crtNode] ) {
                if( !visited[node] )
                    nodes.push( node );
            }
        }

        //return traversal;  // returnam vectorul parcurgerii
    }

    static vector<int> BFS( const vector<vector<int>>& adjacencyList, int startNode, vector<bool>& visited )
    {
        int        nrNodes = adjacencyList.size();  // numarul de noduri ale grafului
        queue<int> nodes;
        nodes.push( startNode );    // adaugam nodul de start in coada
        visited[startNode] = true;  // vizitam nodul de start

        vector<int> traversal( nrNodes );  // vectorul in care retinem parcurgerea
        int         nrNodesTraversed = 0;  // numarul de noduri vizitate

        while( !nodes.empty() ) {
            // scoatem primul nod din coada
            int crtNode = nodes.front();
            nodes.pop();

            traversal[nrNodesTraversed++] = crtNode;  // operator postfixat; adaugam nodul la parcurgere
            // bagam vecinii nevizitati in coada
            for( auto node : adjacencyList[crtNode] ) {
                if( !visited[node] ) {
                    visited[node] = true;  // vizitam vecinul
                    nodes.push( node );
                }
            }
        }

        return traversal;  // returnam vectorul parcurgerii
    }
};

void solveDfs()
{
    int      N, M;
    ifstream in( "dfs.in" );
    in >> N >> M;
    vector<vector<int>> adjacencyList( N + 1 );

    int x, y;
    for( int i = 0; i < M; ++i ) {
        in >> x >> y;
        adjacencyList[x].push_back( y );
        adjacencyList[y].push_back( x );
    }

    int          nrComponents = 0;
    vector<bool> visited( N + 1 );
    ofstream     out( "dfs.out" );
    for( int startNode = 1; startNode <= N; ++startNode )
        if( !visited[startNode] ) {
            ++nrComponents;
            Algorithms::DFS( adjacencyList, startNode, visited );
            /*out << "\nComponenta #" << nrComponents << ": ";
            for( auto node : traversal )
                out << node << ' ';*/
        }

    out << nrComponents;
}

int main()
{
    solveDfs();
}