Difference between revisions of "Solução: Problema do grafo conexo (Jandson Santos)"

#ifndef _VERTICE_H_
#define _VERTICE_H_
 
#include <iostream>
#include <vector>
 
using namespace std;
 
class Vertice
{
   private:
      vector<int> adjacencias;
      bool visitado;
   public:
      Vertice();
      void setAdjacencia(int x);
      int getAdjacencia(int x);
      bool consultaAdjacencia(int x);
      void setVisitado(bool x);
      bool getVisitado();
      unsigned int getQtdeAdjacencias();
};
 
#endif /*_VERTICE_H_*/
 
Vertice::Vertice()
{
}
 
void Vertice::setAdjacencia(int x)
{
   adjacencias.push_back(x);
}
 
int Vertice::getAdjacencia(int x)
{
   return adjacencias[x];
}
 
bool Vertice::consultaAdjacencia(int x)
{
   int i;
   for(i=0; i<((int) adjacencias.size()); i++)
   {
      if(adjacencias.at(i) == x)
      {
         return true;
      }
   }
   return false;
}
 
void Vertice::setVisitado(bool x)
{
   visitado = x;
}
 
bool Vertice::getVisitado()
{
   return visitado;
}
 
unsigned int Vertice::getQtdeAdjacencias()
{
   return (int) adjacencias.size();
}
 
 
 
#ifndef _GRAFO_H_
#define _GRAFO_H_
 
#include <iostream>
#include <cstdlib>
#include <vector>
#include "Vertice.cpp"
 
using namespace std;
 
class Grafo
{
   private:
      vector<Vertice> lVertices;
      int tamGrafo;
   public:
      Grafo(int t);
      void lerEntradas(int qtde);
      Vertice getVertice(int i);
      int conexo();
};
 
#endif /*_GRAFO_H_*/
 
Grafo::Grafo(int t)
{
   int i;
   tamGrafo = t;
   for(i=0; i<t; i++)
   {
      lVertices.push_back(Vertice());
   }
}
 
Vertice Grafo::getVertice(int i)
{
   return lVertices[i];
}
 
void Grafo::lerEntradas(int qtde)
{
   int x, y;
   while(qtde--)
   {
      cin >> x;
      cin >> y;
      lVertices[x].setAdjacencia(y);
      lVertices[y].setAdjacencia(x);
   }
}
 
int Grafo::conexo()
{
   vector<Vertice> pilha;
   unsigned int i, y;
   Vertice topo;
   for(i=0; i<lVertices.size(); i++)
   {
      lVertices[i].setVisitado(false);
   }
   pilha.clear();
   topo = lVertices[0];
   topo.setVisitado(true);
   pilha.push_back(topo);
   while (!pilha.empty())
   {
      topo = pilha.back();
      i=0;
      while(i<topo.getQtdeAdjacencias())
      {
         y = topo.getAdjacencia(i);
         if (lVertices[y].getVisitado())
         {
            i++;
         }
         else
         {
            lVertices[y].setVisitado(true);
            pilha.push_back(lVertices[y]);
            topo = pilha.back();
            i=0;
         }
      }
      pilha.pop_back();
   }
   for(i=0; i<((int) lVertices.size()); i++)
   {
      if (!lVertices[i].getVisitado())
      {
         return false;
      }
   }
   return true;
}
 
int main ()
{
   int tamGrafo, qtdeArestas;
   cin >> tamGrafo;
   cin >> qtdeArestas;
   Grafo g(tamGrafo);
   g.lerEntradas(qtdeArestas);
   cout << g.conexo() << endl;
}