PAT Advanced 1094 The Largest Generation: BFS

Overview

PAT Advanced 1094 The Largest Generation: use BFS, the key is to decide when the nodes in the BFS queue are all and the only nodes at that level/generation.

PAT Advanced 1094 The Largest Generation

A family hierarchy is usually presented by a pedigree tree where all the nodes on the same level belong to the same generation. Your task is to find the generation with the largest population.

Input Specification:

Each input file contains one test case. Each case starts with two positive integers N (<100) which is the total number of family members in the tree (and hence assume that all the members are numbered from 01 to N), and M (<N) which is the number of family members who have children. Then M lines follow, each contains the information of a family member in the following format:

ID K ID[1] ID[2] … ID[K]

where ID is a two-digit number representing a family member, K (>0) is the number of his/her children, followed by a sequence of two-digit ID’s of his/her children. For the sake of simplicity, let us fix the root ID to be 01. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in one line the largest population number and the level of the corresponding generation. It is assumed that such a generation is unique, and the root level is defined to be 1.

Sample Input:

23 13
21 1 23
01 4 03 02 04 05
03 3 06 07 08
06 2 12 13
13 1 21
08 2 15 16
02 2 09 10
11 2 19 20
17 1 22
05 1 11
07 1 14
09 1 17
10 1 18

Sample Output:

9 4

Logo

Solution: BFS

BFS is easy to come up with, but the key is to decide when the nodes in the BFS queue are all and the only nodes at that level/generation. This could be tested by checking the head node in the queue, whether its level is the same as the one just processed (i.e., the number of nodes at this processed level are already recorded). The following C++ code is accepted by the PAT OJ to pass this  1094 The Largest Generation problem:

#include <iostream>
#include <vector>
#include <queue>

using std::cin;
using std::cout;
using std::vector;
using std::queue;

vector<vector<int>> tree;
queue<int> q;
vector<int> level;

int main() {
	int n, m, k;
	int parent, child;

	cin >> n >> m;
	tree.resize(n + 1);
	level.resize(n + 1);

	for (int i = 0; i < m; ++i) {
		cin >> parent >> k;
		for (int j = 0; j < k; ++j) {
			cin >> child;
			tree[parent].push_back(child);
		}
	}

	int maxLevel = 0, maxLevelCounts = 0;
	int generationProcessed = 0;

	q.push(1);
	level[1] = 1;

	while (!q.empty()) {
		if (level[q.front()] != generationProcessed) {
			if (q.size() > maxLevelCounts) {
				maxLevelCounts = q.size();
				maxLevel = level[q.front()];
			}
			generationProcessed = level[q.front()];
		}

		int curr = q.front(); q.pop();

		for (int i = 0, len = tree[curr].size(); i < len; ++i) {
			level[tree[curr][i]] = level[curr] + 1;
			q.push(tree[curr][i]);
		}
	}
	cout << maxLevelCounts << ' ' << maxLevel;

	return 0;
}

To recap the key notes to keep in mind:

  1. This is a tree problem, not a graph, we do not need those flags for visited or not status
  2. The key is at each iteration of the BFS, we need to firs test and decide whether the current queue contains all and only the nodes at its level
  3. We can use two queues to solve this problem too, if you are interested, see this post: LeetCode Binary Tree Zigzag Level Order Traversal: 2 Methods of BFS and DFS as well

Summary

PAT Advanced 1094 The Largest Generation: use BFS, the key is to decide when the nodes in the BFS queue are all and the only nodes at that level/generation.

Written on May 23, 2015