将路径数组变为统计数组

// c++.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>
#include <functional>

using namespace::std;
class Solution {
public:
	/**
	*	将路径数组变为统计数组
	*	输入：代表一张图的数组paths
	*  len path的长度
	*	将paths数组变为距离数组numArr
	*/
	void pathArrToNumArr(vector<int>& vec, int len) {
		int cap = 0;
		for (int i = 0; i < vec.size(); ++i) {
			if (vec[i] == i) {
				cap = i;
				break;
			}
		}

		// 采用层序遍历，设置两个队列
		// 当 first_q 队列为空时，表示一层遍历完毕
		// second_q 用来装下一层的节点
		//               1
		//               |
		//               9
		//             / | \
		//            0  3  7   first_q （装载第 i 层节点）
		//           / \
		//          4   8       second_q（装载第 i + 1 层节点）
		//         / \   \
		//        2   5   6
		deque<int> first_q;
		deque<int> second_q;
		first_q.push_back(cap);
		deque<int> result;
		int count = 0;
		while (first_q.empty() == false) {
			int tmp = first_q.front();
			first_q.pop_front(); // 从第 i 层中出一个节点
			for (int i = 0; i < vec.size(); ++i) {
				if (vec[i] == tmp && vec[i] != i) {
					++count; // 统计该节点的孩子数
					second_q.push_back(i); // 把孩子节点加入到 second_q 队列
				}
			}
			// 如果 first_q 不为空，说明我们还没有遍历完一层
			if (first_q.empty() == false){ 
				continue; // 继续 while 循环，直至 first_q 队列为空，这时我们以完成第 i 层的遍历
			}
			else{
				first_q = second_q; // 把第 i + 1 层节点赋给 first_q 队列
				second_q.clear(); // 
				result.push_back(count); // 把第 i 层的孩子数加入结果集
				count = 0;
			}
		}
		result.push_front(1); // 首都到首都的距离（1）放入结果集的开始
		while (result.size()>vec.size())result.pop_back();
		while (result.size()<vec.size())result.push_back(0);
		int length = vec.size();
		vec.clear();
		for (int i = 0; i < length; ++i){
			vec.push_back(result[i]);
		}
	}
};

int main() {
	vector<int> vec = { 0 };
	Solution obj;
	obj.pathArrToNumArr(vec, vec.size());

	return 0;
}