Cod sursa(job #1932648)

Utilizator Robert29FMI Tilica Robert Robert29 Data 19 martie 2017 22:38:39
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.22 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream cin ("dfs.in");
ofstream cout ("dfs.out");
class GrafNeorientat
{
    int nrNoduri, nrMuchii;
    vector<int> muchii[100001];
    public:
    int GetNrNoduri()
    {
        return nrNoduri;
    }
    int GetNrMuchii()
    {
        return nrMuchii;
    }
    void CitesteGraf()
    {
        cin >> nrNoduri >> nrMuchii ;
        for(int i = 1; i <= nrMuchii; ++i)
        {
            int nod1, nod2;
            cin >> nod1 >> nod2;
            muchii[nod1].push_back(nod2);
            muchii[nod2].push_back(nod1);
        }
    }
    vector<int> BFS(int nodStart)
    {
        queue<int> q;
        q.push(nodStart);
        vector<int> dist;
        for(int i = 0 ; i <= nrNoduri; ++i)
        {
            dist.push_back(0);
        }
        while(!q.empty())
        {
            int nod = q.front();
            for(int i = 0; i < muchii[nod].size(); ++i)
            {
                int vecin = muchii[nod][i];
                if(vecin == nodStart)
                {
                    continue;
                }
                if(dist[vecin] == 0)
                {
                    q.push(vecin);
                    dist[vecin] = dist[nod] + 1;
                }
            }
            q.pop();
        }
        return dist;
    }
    void DFS(int nod, vector<bool> &viz)
    {
        viz[nod] = true;

        for(int i = 0; i < muchii[nod].size(); ++i)
        {
            int vecin = muchii[nod][i];
            if(!viz[vecin])
            {
                DFS(vecin, viz);
            }
        }
    }
    int ComponenteConexe()
    {
        vector<bool> viz;
        for(int i = 0; i <= nrNoduri; ++i)
        {
            viz.push_back(false);
        }

        int nr = 0;
        for(int i = 1; i <= nrNoduri; ++i)
        {
            if(!viz[i])
            {
                DFS(i, viz);
                ++nr;
            }
        }
        cout << nr;
        return nr;
    }
    void MatriceaDrumurilor()
    {

    }
};

int main()
{
    GrafNeorientat graf;
    graf.CitesteGraf();

    graf.ComponenteConexe();
    return 0;
}