Conexidade de um grafo

Aplicação: Descobrir se um grafo é conexo ou não. 

http://br.spoj.pl/problems/ENERGIA/

Ficha Técnica:
Problema: Descobrir se um grafo é conexo
Algoritmo: Busca em Profundidade usando recursão
Estrutura de Dados: Lista de Adjacência usando vector
Observações:
Compared to the other base standard sequence containers (deques and lists), vectors are generally the most efficient in time for accessing elements and to add or remove elements from the end of the sequence. For operations that involve inserting or removing elements at positions other than the end, they perform worse than deques and lists, and have less consistent iterators and references than lists.
Complexidade: O(V+E)
Tempo:  0.14
Linguagem: C++
Memória:  2.8M

Busca em Profundidade usando recursão usando lista de adjacência C++

#include <iostream>
#include <vector>
#include <stack>
#define MAX 101
using namespace std;
//representacao de grafo usando lista de adjacência
vector <int> lista[MAX]; 
//marc[i] = true significa que o vetor foi visitado
bool marc[MAX];
//contador de numero de visitas
int cont;

void bp(int u){
 vector <int>::iterator it; 
 cont++;
 for(it = lista[u].begin(); it!=lista[u].end(); it++){
    if(!marc[*it]){
      marc[*it]=true;
      bp(*it);
    }
 } 
 

}
int main(){
 int n,m,u,v,i,a,b,teste=1;
 while(true){
   cin >> n >> m; 
   if(n==0 && m==0) break;
   for(i=1;i<=n;i++){ 
     marc[i]=false;
     lista[i].clear();
          }
   for(i=1;i<=m;i++){
     cin >> a >> b;
     lista[a].push_back(b);
     lista[b].push_back(a);
   }
  
   marc[1] = true;
   cont = 0;
   bp(1);
  
  
   cout << "Teste " << teste++ << endl;
   if(cont==n)
    cout << "normal" << endl;
   else
           cout << "falha" << endl;
   cout << endl;
 }
} 

Ficha Técnica:
Problema: Descobrir se um grafo é conexo
Algoritmo: Busca em Profundidade usando pilha
Estrutura de Dados: Lista de Adjacência usando matriz
Complexidade: O(V+E)
Tempo:  0.02
Linguagem: C
Memória:  1.7M

Busca em Profundidade usando pilha e  lista de adjacência em C

#include <stdio.h>
#define MAX 101

int pilha[MAX];
int topo;
int g[MAX][MAX];
int d[MAX];
int marc[MAX];

int inicializa(){
 topo = 0;
}

void push(int x){
 pilha[topo++] = x;
}

int pop(){
 return pilha[--topo];
}

int vazia(){
 return topo==0;
}

int main(){
 int n,m,u,i,v,a,b,cont,teste=1;
 
 while(1){
  scanf("%d %d",&n,&m);
  
  if(n==0 && m==0) break;
  
  for(i=1;i<=n;i++){
   d[i] = 0;
   marc[i]=0; 
  }
  
  for(i=1;i<=m;i++){
   scanf("%d %d",&a,&b);
   g[a][d[a]++]=b;
   g[b][d[b]++]=a;
  }

  inicializa();
  marc[1]=1;
  push(1);
  cont = 0;
  
  while(!vazia()){
   u = pop();
   cont++;
   
   for(i=0;i<d[u];i++){
    v = g[u][i];
    if(marc[v]==0){
     marc[v]=1;
     push(v);
    }
   }
  }
  
  printf("Teste %d\n",teste++);
  
  if(cont==n) printf("normal\n\n");
  else printf("falha\n\n");
  
 }
 
 return 0;
  

}

Ficha Técnica:
Problema: Descobrir se um grafo é conexo
Algoritmo: Busca em Profundidade usando pilha
Estrutura de Dados: Lista de Adjacência usando vector
Complexidade: O(V+E)
Tempo:  0.13
Linguagem: C++
Memória:  2.6M

Busca em Profundidade usando pilha e lista de adjacência em C++

#include <iostream>
#include <vector>
#include <stack>
#define MAX 101
using namespace std;
vector <int> lista[MAX];
vector <int>::iterator it;
stack <int> pilha;
bool marc[MAX];
int main(){
 int n,m,u,v,i,a,b,cont,teste=1;
 while(true){
  cin >> n >> m; 
  if(n==0 && m==0) break;
  for(i=1;i<=n;i++){ 
    marc[i]=false;
     lista[i].clear();
  }
  for(i=1;i<=m;i++){
   cin >> a >> b;
   lista[a].push_back(b);
   lista[b].push_back(a);
  }
  marc[1] = true;
  pilha.push(1);
  cont = 0;
  while(!pilha.empty()){
   u = pilha.top();
   pilha.pop();
   cont++;
   for(it = lista[u].begin(); it!=lista[u].end(); it++){
    if(!marc[*it]){
     marc[*it]=true;
     pilha.push(*it);
    }
   } 
  }
  
  
  cout << "Teste " << teste++ << endl;
  if(cont==n)
   cout << "normal" << endl;
  else
   cout << "falha" << endl;
  cout << endl;
 }
}

2009-10-12 15:26:37  Transmissão de Energia aceito 0.13  2.6M  C++4.0.0-8 

Ficha Técnica:
Problema: Descobrir se um grafo é conexo
Algoritmo:
Estrutura de Dados: Conjuntos Disjuntos
Complexidade:??
Tempo:  0.03
Linguagem: C
Memória:  1.6M

Descobrindo se grafo é conexo usando conjuntos disjuntos

#include <stdio.h>

int p[101];
int ordem[101];

void make_set(int x){
     p[x] = x;
     ordem[x] = 0;
}

int find_set(int x){
    if( x!= p[x] ) 
      p[x] = find_set(p[x]);
    return p[x];
}

void link(int x,int y){
     if(ordem[x] > ordem[y]){
        p[y] = x;
     }else{
        p[x] = y;
        if(ordem[x]==ordem[y])
          ordem[y]++;
     }
}


void une(int x,int y){
     link(find_set(x),find_set(y));
}


int same_componente(int x,int y){
    if(find_set(x)==find_set(y)) return 1;
    else return 0;
}

int main(){
    int n,m,i,a,b,conexo,teste=1,cont;
    
    while( scanf("%d %d",&n,&m) > 0 ){
           if(n+m==0) break;
           
           for(i=1;i<=n;i++){
             make_set(i);
           }
           
           cont = 0;
           for(i=1;i<=m;i++){
              scanf("%d %d",&a,&b);
              if( !same_componente(a,b) )
               cont++;
        une(a,b);
           }
           
           
           printf("Teste %d\n",teste++);
           if(cont==n-1) printf("normal\n\n");
           else printf("falha\n\n");
    }
    return 0;
    
}

2009-10-12 15:01:21     Transmissão de Energia    aceito 0.03     1.6M     C