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: *****  / 7
SłabyŚwietny
Nadesłany przez Emil Hotkowski, 22 stycznia 2012 15:57
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.

euler_cykl_1_c.cpp:
/*
GRAF NIESKIEROWANY !!!!!
Założenie : Graf posiada cykl Eulera , a wierzcholek od ktorego zaczynamy jest poczatkiem tego cyklu
Copyright @ Rjiuk Yagami - Emil Hotkowski
www.algorytm.org
*/

#include <vector>
#include <iostream>
#include <set>

#define MX 10000

using namespace std;

int byc[MX][MX];//przebyte wierzcholki
vector<int>t[MX];//graf
vector<int>wynik;//kolejne wierzcholki w cylku

int dfs(int v)
{
    while(!t[v].empty())
    {
        int w = t[v].back();
        t[v].pop_back();
        if(byc[v][w] == 0)
        {
            byc[v][w]=1;
            byc[w][v]=1;
            dfs(w);
            wynik.push_back(w);
        }
   
    }
}

//graf nieskierowany
int main(int argc, char *argv[])
{
    int n , m,po;//n - wieszcholkow   m - krawedzi po - poczatek cyku Eulera
    cin >> n >> m;//wprwoadzamy dane
    for(int i=1; i<=m; i++)       // wprowadz wierzcholki i krawedzie
    {
        int a, b;//polaczenia 
        cout << "Krawedz " << i << ": ";//ktora z kolei krawedz
        cin >> a >> b;//polaczenie a i b
        t[a].push_back(b);
        t[b].push_back(a);
    }

    cout << "od ktorego wierzchołka zaczac ? : ";//start cyklu Eulera
    cin >> po; 
    cout << "\n\n" << po << " ";
    dfs(po);
    for(int i = 0 ; i < m;i++)
    {
        cout << wynik.back() << " ";
        wynik.pop_back();
    }

    system("PAUSE");
    return EXIT_SUCCESS;
}



Dodaj komentarz