• API
• FAQ
• Tools
• Trends
• Archive
daily pastebin goal
4%
SHARE
TWEET

a guest May 7th, 2017 2 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. #include <vector>
3. #include <queue>
4. using namespace std;
5.
6. /* The graphs used in the post's diagrams
7.    have node indexing which starts at 1.
8.    Since arrays and vectors in C++ use
9.    0-based indexing, we subtract 1 from the
10.    indices used in the input, and add 1
11.    to the indices printed in the output. */
12.
13. /* This graph can support 10000 nodes
14.    numbered from 1 to 10000 inclusive. */
15. bool visited[10000] = {false};
16.
17. /* Each vector of integers represents
18.    an individual node and the nodes it
19.    is connected with. */
21.
22. int main () {
23.     /* Take the number of nodes in the graph
24.        and the number of edges in the graph as input. */
25.     int nodeCount, edgeCount;
26.     cin >> nodeCount >> edgeCount;
27.
28.     /* Fill the adjacency list with unconnected nodes. */
29.     for (int i = 0; i < nodeCount; i++) {
30.         vector<int> node;
32.     }
33.
35.        using the input as a guide. */
36.     for (int i = 0; i < edgeCount; i++) {
37.         int n1, n2;
38.         cin >> n1 >> n2;
39.         n1--;
40.         n2--;
43.     }
44.
45.     /* Take the index of the starting node. */
46.     int startIndex;
47.     cin >> startIndex;
48.     startIndex--;
49.
50.     /* First, push the index of the starting node
51.        onto the traversal queue - this structure
52.        holds the indices of the nodes which we
53.        will go on to visit. */
54.     queue<int> bfsQueue;
55.     bfsQueue.push(startIndex);
56.     while (!bfsQueue.empty()) {
57.         /* Take the index of the node that is first
58.            in the queue - this is the value which
59.            has been in the queue the longest (that is,
60.            the value at the 'front' of the queue). */
61.         int index = bfsQueue.front();
62.         bfsQueue.pop();
63.         visited[index] = true;
64.         cout << index+1 << "\n";
65.
66.         for (int i = 0; i < adjList[index].size(); i++) {