#include <iostream>
#include <queue>

using namespace std;

struct edge{
	int s;
	int t;
};

class Graph{
	private:
		int** adjMatrix;
		int n;				//liczba węzłów
	public:
		Graph(int n, int m, edge edges[], bool directed = false){
        this->n=n;
        adjMatrix = new int*[n];
            for (int i = 0; i < n; ++i) {
               adjMatrix[i]=new int[n];
                }
            for(int i=0; i<n;i++){
                for(int j=0; j<n;j++)
                    adjMatrix[i][j]=0;
            }
            for(int i=0; i<m;i++){
                adjMatrix[edges[i].s][edges[i].t]=1;
                adjMatrix[edges[i].t][edges[i].s]=1;
            }

		};	//tworzy graf w oparciu o pdaną listę krawędzi

		int edgeCnt(){
		    int m=0;
		    for(int i=0; i<n ;i++){
                for(int j=0; j<n;j++){
                    if(adjMatrix[i][j]==1)
                        m++;
                        }
                }
             m=m/2;
           return m;
		};					//zwraca liczbę krawędzi

		int nodeCnt(){
            return n;
		}; 					//zwraca liczbę węzłów

		void insertEdge(int u, int v){
            adjMatrix[u][v]=1;
		};			//wstawia krawędź

		void deleteEdge(int u, int v){			//usuwa krawędź
            adjMatrix[u][v]=0;
            };
		bool check(int u, int v){
            if(adjMatrix[u][v]==0)
                return 0;
            else
                return 1;
		};			//sprawdza czy istnieje krawędź

		void bfs(int s){
            int m=edgeCnt();
            int* odwiedzone = new int[m];
            for (int i = 0; i < m; ++i) {
                odwiedzone[i] = 0;
                }
            odwiedzone[s] = 1;

            queue<int> kolejka;
            kolejka.push(s);

            int aktualny;
            while (!kolejka.empty()){
                aktualny = kolejka.front();
                cout << aktualny << " ";
                for (int i = 0; i < n; ++i) {
                    if (adjMatrix[aktualny][i] == 1 && odwiedzone[i] == 0) {
                        odwiedzone[i] = 1;
                        kolejka.push(i);
                }
            }
                kolejka.pop();
                }
                };
                //wyświetla węzły w porządku odwiedzenia




		void dfs(int s){
		    int m=edgeCnt();

		};
		//wyświetla węzły w porządku odwiedzenia




		friend ostream& operator<<(ostream& out, Graph& g){
            for(int i=0; i<g.nodeCnt();i++){
                for (int j=0; j<g.nodeCnt();j++){
                    out << "["<<i<<"]"<<"["<<j<<"] "<<g.adjMatrix[i][j]<<endl;
                }
            }

		};
	//	~Graph();
	//inne potrzebne/pomocnicze metody składowe
};


int main(int argc, char** argv) {
	int n = 10, m =14;
	edge undirectedConnectedGraph[]={{0,1}, {0,4}, {0,6}, {1,2}, {1,7}, {2,3}, {2,8}, {3,5}, {3,9}, {4,7}, {5,8}, {6,7}, {7,8}, {8,9}};
	Graph g(n,m,undirectedConnectedGraph);
    cout<<g;
    cout<<"BFS: ";
	g.bfs(0);
	cout<<"DFS: ";
//	g.dfs(0);
   /* int spr =g.edgeCnt();
    cout<<spr;*/
	return 0;
}






	odwiedzone[v] = 1;
	cout << v << " ";
	for (int i = 0; i < N; ++i) {
		if (graf[v][i] == 1 && odwiedzone[i] == 0) {
			visit(i, odwiedzone, graf, N);
		}
	}
	void printDFS(int** graf, int N, int start) {
	int* odwiedzone = new int[N];

	for (int i = 0; i < N; ++i) {
		odwiedzone[i] = 0;
	}

	for (int i = 0; i < N; ++i) {
		if (odwiedzone[i] == 0) {
			visit(i, odwiedzone, graf, N);
		}
	}

	cout << endl;
}