Simple implementation of a BFS https://en.wikipedia.org/wiki/Breadth-first_search https://upload.wikimedia.org/wikipedia/commons/3/33/Breadth-first-tree.svg Time complexity is O(|V| + |E|). According to Wikipedia O(|E|) may vary from O(|V|) to O(|V|^2).

BFS.cpp

// BFS - Breadth First Search
// author: Rodrigo Alves
// As explained on Wikipedia https://en.wikipedia.org/wiki/Breadth-first_search
#include <cstdio>
#define Mark(A, pos) (A[pos] = 1)

class Node {
public:
    int value;
    Node* next;
    Node(int v) : value(v), next(NULL) {}
};

class List {
public:
    Node* tail;
    Node* head;
    int size;

    List() { tail = head = NULL; }
    bool isEmpty();
    void insert(int n);
    void print();
    int counter();
};

bool List::isEmpty() { return head == NULL;}

void List::insert(int n)
{
    Node* newNo = new Node(n);

    if (isEmpty()) {
        head = tail = newNo;
    } else {
        tail -> next = newNo;
        tail = tail -> next;
    }
    size++;
}

void List::print()
{
    Node* aux = head;
    while (aux != NULL) {
        printf("%d", aux -> value);
        if (aux -> next) printf(", ");
        aux = aux -> next;
    }
}

int List::counter()
{
    Node* aux = head;
    int c = 0;
    while(aux != NULL) {
      c++;
      aux -> next;
    }
    return c;
}

class Queue {
public:
    Node *begin;
    int size;

    Queue() : begin(NULL), size(0) {}
    bool isEmpty() { return begin == NULL; }
    void enqueue(int n);
    int dequeue();
};

void Queue::enqueue(int n)
{
    Node* no = new Node(n);
    Node* aux = begin;

    if (isEmpty()) {
        begin = no;
    } else {
        while(aux -> next != NULL) {
            aux = aux -> next;
        }
        aux -> next = no;
    }
    size++;
}

int Queue::dequeue()
{
    if (!isEmpty()) {
        int val = begin -> value;
        begin = begin -> next;
        size--;
        return val;
    }
}

void printGraph(List* Adj, int N)
{
    for (int j = 1; j < N; j++) {
        printf("Vertex %d: ", j);
        Adj[j].print();
        printf("\n");
    }
}

int main()
{
    freopen("graph.txt", "r", stdin);
    int T, N, Q, E, x, vertex; bool empty;
    scanf("%d", &T);

    while (T--) {
        scanf("%d", &N);
        int i = 0, j = 0, t;
        int* marked;
        List* Adj = new List[N];

        for (; i < N; i++) {
            scanf("%d", &Q);
            while (Q--) {
                scanf("%d", &x);
                Adj[i].insert(x);
            }
        }

        printGraph(Adj, N);

        scanf("%d", &E);
        while (E--) {
            Queue A;
            marked = new int[N];
            scanf("%d", &vertex);
            A.enqueue(vertex);
            Mark(marked, vertex);
            empty = false;

            while (!A.isEmpty()) {
                if (Adj[vertex].isEmpty()) {
                    empty = true;
                    break;
                }

                t = A.dequeue();
                Node* aux = Adj[t].head;

                while (aux != NULL) {
                    if (!marked[aux -> value]) {
                        Mark(marked, aux -> value);
                        A.enqueue(aux -> value);
                    }

                    aux = aux -> next;
                }
            }
        }
    return 0;
    }
}

Graph.txt

1

8
0
3 2 3 4
2 5 6
0
2 7 8
2 9 10
0
2 11 12
0