#include <iostream>
#include <vector>
#include <cstdio>
#include <list>
#include <queue>

using namespace std;

class Graph{
private:
    int V;          // 节点数量
    list<int>* adj; // 邻接矩阵
    int* inDegree;  // 入度数组
    queue<int>* q;  // 入度位0的队列

public:
    Graph(int v) {
        this->V = v;
        this->adj = new list<int>[v];
        this->inDegree = new int[v];
        for(int i=0; i<v; i++) {
            this->inDegree[i] = 0;
        }
    }
    ~Graph() {
        delete [] this->adj;
        delete [] this->inDegree;
    }

    void addEdge(int v, int w){
        this->adj[v].push_back(w);
        inDegree[w]++;
    }

    bool topoSort() {
        for (int i=0; i<this->V; i++) {
            if (inDegree[i] == 0) {
                q->push(i);
            }
        }
        int cnt = 0, v;
        while (!q->empty()) {
            v = q->front();
            q->pop();
            printf("%d ", v);
            cnt ++;
            for (list<int>::iterator i=adj[v].begin(); i!=adj[v].end(); ++i) {
                if (!--inDegree[*i]) {
                    q->push(*i);
                }
            }
        }
        if (cnt == 0) {
            return true;
        }
        else {
            return false;
        }
    }

    void BFSUtil(int v, bool visited[]) {
        queue<int> que;
        visited[v] = true;
        que.push(v);
        int node;
        while (!que.empty()) {
            node = que.front();
            printf("%d ", node);
            que.pop();
            for(list<int>::iterator i=adj[node].begin(); i!=adj[node].end(); i++) {
                if (!visited[*i]) {
                    visited[*i] = true;
                    que.push(*i);
                }
            }
        }
    }

    void BFS(int v) {
        bool *visited = new bool[v];
        for (int i=0; i<V; i++) {
            visited[i] = false;
        }
        BFSUtil(v, visited);
    }

    void DFSUtil(int v, bool visited[]) {
    }

    void DFS(int v) {
    }

    
};



int main(int argc, char** argv) {
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 3);

    g.BFS(2);
}