8063591571

Listing 2.3: Główna część programu służącego do konwertowania reprezentacji grafu // Zarówno dla wierzchołków, jak i dla krawędzi nie potrzebne są żadne dodatkowe // informacje

01    struct Empty { };

02    int mainO {

03    int n, m, b, e;

// Wczytaj liczbę wierzchołków i krawędzi w grafie

04    cin >> n >> m;

// Skonstruuj graf o odpowiednim rozmiarze, nie zawierający dodatkowych // informacji dla wierzchołków ani krawędzi

05    Graph<Empty, Empty> gr (n) ;

06    REP(x, m) {

// Wczytaj początek i koniec kolejnej krawędzi

07    cin >> b >> e;

// Dodaj do grafu krawędź skierowaną z wierzchołka b do e

08    gr.EdgeDCb, e);

09    }

// Wypisz graf

10    gr.WriteO;

11    return 0;

12}_

Listing 2.4: Pełny kod źródłowy programu konwertującego reprezentację grafu

01    #include <cstdio>

02    #include <iostream>

03    #include <algorithm>

04    #include <string>

05    #include <vector>

06    using namespace std;

07    typedef vector<int> VI;

08    typedef long long LL;

09    #define FOR(x, b, e) for (int x = b; x <= (e); ++x)

10    #define FORD(x, b, e) for(int x = b; x >= (e); —x)

11    #define REP(x, n) for(int x = 0; x < (n); ++x)

12    #define VAR(v, n) __typeof(n) v = (n)

13    #define ALL(c) (c).begin(), (c).end()

14    #define SIZE(x) ((int)(x).size())

15    #define FOREACH(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)

16    #define PB push_back

17    #define ST first

18    #define ND second

19    template <class V, class E> struct Graph {

20    struct Ed : E {

21    int v;

22    Ed(E p, int w) : E(p), v(w) { }

23    };

24    struct Ve : V, vector<Ed> { };