Cod sursa(job #2786585)

Utilizator blxqnAlina Voiculescu blxqn Data 21 octombrie 2021 10:54:51
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.52 kb
#include <bits/stdc++.h>
using namespace std;

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

class Graph
{
    int NumberOfNodes;
    int NumberOfEdges;
    bool Oriented;
    vector<vector<int>> AdjacencyList;

    public:
        Graph();
        Graph(int, int, bool);

        void Build();
        void BFS(int, int[]);
        void DFS(int, bool[]);
        int NumberOfConnectedComponents();
};


int main()
{
    int NumberOfNodes, NumberOfEdges;
    fin >> NumberOfNodes >> NumberOfEdges;

    Graph G(NumberOfNodes, NumberOfEdges, 0);
    G.Build();

    fout << G.NumberOfConnectedComponents();

/*  ----------------------------BFS----------------------------
    int NumberOfNodes, NumberOfEdges, StartNode;
    fin >> NumberOfNodes >> NumberOfEdges >> StartNode;

    Graph G(NumberOfNodes, NumberOfEdges, true);
    G.Build();

    int Distance[NumberOfNodes];
    StartNode--;
    G.BFS(StartNode, Distance);

    for (int i = 0; i < NumberOfNodes; i++)
        fout << Distance[i] << " ";

    ----------------------------BFS----------------------------*/

    fin.close();
    fout.close();

    return 0;
}




Graph::Graph() : NumberOfNodes(0), NumberOfEdges(0), Oriented(0) { }

Graph::Graph(int _NumberOfNodes, int _NumberOfEdges, bool _Oriented) : NumberOfNodes(_NumberOfNodes), NumberOfEdges(_NumberOfEdges), Oriented(_Oriented)
{
    NumberOfNodes = _NumberOfNodes;
    NumberOfEdges = _NumberOfEdges;
    Oriented = _Oriented;

    for (int i = 0; i < _NumberOfNodes; i++)
        AdjacencyList.push_back( {} );
        //AdjacencyList.push_back(vector<int>());
}

void Graph::Build()
{
    for (int i = 0; i < NumberOfEdges; i++)
    {
        int FirstNode, SecondNode;
        fin >> FirstNode >> SecondNode;
        FirstNode--;
        SecondNode--;

        AdjacencyList[FirstNode].push_back(SecondNode);
        if (!Oriented)
            AdjacencyList[SecondNode].push_back(FirstNode);
    }
}

void Graph::BFS(int StartNode, int Distance[])
{
    bool Visited[NumberOfNodes];
    queue<int> BFSQueue;

    for(int i = 0; i < NumberOfNodes; i++)
    {
        Visited[i] = 0;
        Distance[i] = -1;
    }

    Visited[StartNode] = 1;
    Distance[StartNode] = 0;
    BFSQueue.push(StartNode);

    while (!BFSQueue.empty())
    {
        int CurrentNode = BFSQueue.front();

        for (unsigned int i = 0; i < AdjacencyList[CurrentNode].size(); i++)
        {
            int AdjacentNode = AdjacencyList[CurrentNode][i];

            if (!Visited[AdjacentNode])
            {
                Visited[AdjacentNode] = 1;
                Distance[AdjacentNode] = Distance[CurrentNode] + 1;
                BFSQueue.push(AdjacentNode);
            }
        }
        BFSQueue.pop();
    }
}

void Graph::DFS(int StartNode, bool Visited[])
{
    Visited[StartNode] = 1;

    for (unsigned int i = 0; i < AdjacencyList[StartNode].size(); i++) //parcurg vecinii nodului
    {
        int NextNode = AdjacencyList[StartNode][i];
        if (!Visited[NextNode])
            DFS(NextNode, Visited);
    }
}

int Graph::NumberOfConnectedComponents()
{
    bool Visited[NumberOfNodes];
    int _NumberOfConnectedComponents = 0;

    for (int i = 0; i < NumberOfNodes; i++)
        Visited[i] = 0;

    for (int i = 0; i < NumberOfNodes; i++)
    {
        if (!Visited[i])
        {
            DFS(i, Visited);
            _NumberOfConnectedComponents++;
        }
    }

    return _NumberOfConnectedComponents;
}