algorytm.org

Implementacja w C/C++

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Cykl Eulera - Implementacja w C/C++
Ocena użytkownikóww: *****  / 2
SłabyŚwietny
Nadesłany przez Emil Hotkowski, 29 stycznia 2013 21:15
Kod przedstawiony poniżej przedstawia główną część rozwiązania problemu.
Pobierz pełne rozwiązanie.

Jeżeli nie odpowiada Ci sposób formatowania kodu przez autora skorzystaj z pretty printer'a i dostosuj go automatycznie do siebie.

cykl_eulera.cpp:
//Wyszukiwanie cyklu Eulera w grafie
//www.algorytm.org

#include <iostream>
#include <cstdio>
#include <map>
#include <stack>
#include <set>
#include <list>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#define FOR(i,p,k) for(int i = (p);i<(k);i++)
#define PB push_back

using namespace std;

struct krawedz//nasza struktura reprezentujaca krawedzie w grafie
{
 int x;//dokad porawdzi krawedz
 list<krawedz>::iterator przeciwna;//iterator do przeciwnej krawedzi       
 };
//iterato pomoze nam w czsie stalym usuwac krawedzi z grafu :)

vector<int> CE;//tu wrzucamy kolejne wierzcholki naszego cyklu 
stack<int> STOS;//stos na potrzeby naszego algorytmu
int n,m;//ilosc wierzcholkow i krawedzi
list<krawedz> ZA[1000007];//tutaj trzymamy nasz graf

//pobiera dane od uzytkownika
void dane()
{
 //pobierz liczbe wierzcholkow i krawedzi
 cin>>n>>m;
 FOR(i,0,m)
 {
  int a,b;
  //pobierz indeksy wierzcholkow
  cin>>a>>b;
  krawedz k;//wrzucamy krawedzi do grafu
  k.x=b;
  ZA[a].PB(k);
  k.x=a;
  ZA[b].PB(k);  
  list<krawedz>::iterator it;
  it=ZA[a].end();it--;
  ZA[b].back().przeciwna=it;//wrzucamy iterator do przeciwnej
  it=ZA[b].end();it--;
  ZA[a].back().przeciwna=it;       
 }  
}

//wyszukuje cykl Eulera
void cykle()
{
 STOS.push(1);
 while(STOS.size())
 {
  int v=STOS.top();
  if(!ZA[v].empty())
  {
    list<krawedz>::iterator it, it_przeciwna;
    it = ZA[v].begin(); //wez pierwsza krawedz dla aktualnego wierzcholka
    it_przeciwna = it->przeciwna;
    int u = it->x;
    STOS.push(u);    //poloz ja na stosie
    ZA[v].erase(it); //usuwamy przeciwne
    ZA[u].erase(it_przeciwna);   
    v=u;   
    }
  else//jezeli wierzcholek nie ma juz krawedzi wychodzacych
  {
   STOS.pop();
   CE.PB(v);// to wrzucamy go na vector
  }                
 }    
}

//wypisuje wynik
void wys()
{
  FOR(i,0,CE.size())
  cout<<"-> "<<CE[i]<<"\n";
}

//glowne wejscie do programu
int main()
{
 dane();   //pobierz dane
 cykle();  //wyszukaj cykl Eulera
 wys();    //wypisz wynik
 system("PAUSE");
 return 0;   
}
Dodaj komentarz