Busca em Profundidade

A busca em profundidade é um algoritmo para realizar busca  e travessia numa árvore ou em um grafo. A ideia do algoritmo é começar num nó raiz e explora cada um dos seus ramos  tanto quanto possível antes de retroceder.

Aplicações:

• Descobrir se um grafo é conexo.
• Descobrir se um grafo é bipartido.
• Encontrar componentes fortemente conexas.
• Encontrar articulações.
• Encontrar pontes.
• Encontrar uma ordenação topológica.
• Resolver quebra-cabeças.

Vamos implementar a busca em profundidade utilizando as ferramentas da STL.

#include <iostream>
#include <vector>
#define all(c) (c).begin, (c).end()
#define tr(c,it) for(typeof((c).begin()) it = (c).begin()  ; it != (c).end() ; it++ )
using namespace std;

typedef vector <int> vi;
typedef vector <vi> vvi;
typedef vector <bool> vb;

void dfs(int i, vvi g ,vb & marc, int & cont){
 if( !marc[i] ){
  cont++;
  marc[i] =true;
  tr(g[i],it){
   dfs(*it, g, marc, cont);
  }  
 }
}

int main(){
 int N,M;
 int a,b;
 int cont;
 
 while(1){
  
  cin >> N >> M;
  
  vvi g(N+1);
  
  for(int i =0;i<M;i++){
   cin >> a >> b;
   g[a].push_back(b);
   g[b].push_back(a);
  }
  
  vb marc(N+1,false);  
  
  cont = 0 ;
  dfs(1, g, marc, cont);
  
  if(cont==N)
   cout << "Normal\n" ; 
  else 
   cout << "Falha\n" ;
   
 }
}