CCC '18 J5 - Choose your own path
Source Code
#include <bits/stdc++.h>
#include <iostream>
#include <set>
#include <map>
#include <memory>
#include <stack>
#include <queue>
using namespace std;
typedef struct node{
int data;
vector<shared_ptr<struct node>> children;
}node_t;
int shortest_path(vector<shared_ptr<node_t>> nodes, int level){
level++;
vector<shared_ptr<node_t>> childNodes;
for(auto node : nodes){
if(node->children.size() == 0){
return level;
}else{
for(auto a: node->children){
childNodes.push_back(a);
}
}
}
return shortest_path(childNodes, level);
}
void getReachablePages(shared_ptr<node_t> node, set<int>& pages){
if(pages.find(node->data) == pages.end()){
pages.insert(node->data);
for(auto a : node-> children){
getReachablePages(a, pages);
}
}
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n;
cin >> n;
map <int, shared_ptr<node_t>> pageMap;
for(int i = 0; i < n; i++){
pageMap[i + 1] = make_unique<node_t>();
pageMap[i + 1]->data = i + 1;
}
for(int i = 1; i <= n; i++){
int num = 0;
cin >> num;
for(int j = 0; j < num; j++){
int page = 0;
cin >> page;
pageMap[i]-> children.push_back(pageMap[page]);
}
}
set<int> pages;
getReachablePages(pageMap[1], pages);
if(pages.size() == n){
cout << "Y\n";
}else{
cout << "N\n";
}
int level = 0;
vector<shared_ptr<node_t>> nodesToCheck;
nodesToCheck.push_back(pageMap[1]);
cout << shortest_path(nodesToCheck, level) << "\n";
return 0;
}