#include <iostream>
#include <fstream>
#include <cstdlib>
#include <string>
#include <list>

using namespace std;

class Vertex {
public:
    int nr;
    int dist;
    Vertex* next;
    Vertex(int a, int b, Vertex* c) {
        nr = a;
        dist = b;
        next = c;
    }
};

class Graph {
public:
    Vertex** NL;
    int size;
    int data;
    void AddToNL(Vertex*& H, int nr, int data) {
        Vertex* t = new Vertex(nr, data, H);
        H = t;
    };
    Graph() {
        fstream file;
        file.open("graf.txt", ios::in);
        size;
        data;
        file >> size;

        //LISTA SASIEDZTWA
        NL = new Vertex * [size];
        for (int i = 0; i < size; i++) {
            NL[i] = NULL;
        }
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                file >> data;
                if (data > 0) {
                    AddToNL(NL[i], j, data);
                }
            }
        }
    }

    //PRZESZUKIWANIE W SZERZ
    void BFS(int s) {
        cout << "Przeszukiwanie wszerz" << endl;
        char* colors = new char[size];
        for (int i = 0; i < size; i++) {
            colors[i] = 'w';
        }
        list<int> queue;
        colors[s] = 'g';
        queue.push_back(s);
        while (!queue.empty()) {
            int u = queue.front();
            queue.pop_front();
            Vertex* p = NL[u];
            while (p) {
                if (colors[p->nr] == 'w') {
                    colors[p->nr] = 'g';
                    cout << "Odwiedzonio wierzcholek " << p->nr << endl;
                    queue.push_back(p->nr);
                }
                p = p->next;
            }
            colors[u] = 'b';
        }
    }

    //PRZESZUKIWANIE W GLAB
    char* colors = new char[size];
    void DFS() {
        cout << "Przeszukiwanie w glab" << endl;
        for (int i = 0; i < size; i++) {
            colors[i] = 'w';
        }
        for (int i = 0; i < size; i++) {
            if (colors[i] == 'w')
                visit(i);
        }
    }
    void visit(int s) {
        cout << "Odwiedzono wierzcholek " << s << endl;
        colors[s] = 'g';
        Vertex* p = NL[s];
        while (p) {
            if (colors[p->nr] == 'w') {
                visit(p->nr);
            }
            p = p->next;
        }
        colors[s] = 'b';
    }
};

int main() {
    Graph graph;
    graph.BFS(0);
    cout << endl;
    graph.DFS();
    system("PAUSE");
    return 0;
}