#include<iostream>
#include<vector>
#include<string>
#include<utility> // std::pair, std::make_pair
#include<unordered_map>usingnamespacestd;voidDFS(intdepth,stringkey,unordered_map<string,vector<string>>mp){if(!mp.count(key))// if key does not existreturn;vector<string>values=mp[key];for(inti=0;i<values.size();i++){for(intj=0;j<depth;j++)cout<<"\t";cout<<values[i]<<endl;DFS(depth+1,values[i],mp);}}intmain(){vector<pair<string,string>>input;input.push_back(make_pair("animal","mammal"));input.push_back(make_pair("animal","bird"));input.push_back(make_pair("lifeform","animal"));input.push_back(make_pair("cat","lion"));input.push_back(make_pair("mammal","cat"));input.push_back(make_pair("animal","fish"));unordered_map<string,vector<string>>mp;unordered_map<string,bool>seen;for(autop:input){stringkey=p.first;stringval=p.second;seen[val]=true;if(mp.count(key)){mp[key].push_back(val);}else{vector<string>arr={val};mp[key]=arr;}}// Finding the start point (root node)// 1. Brute force: Use DFS and count the height// 2. If the string ever appeared in the p.second (as a val) then remove from the candidatestringroot="";for(autom:mp){if(!seen.count(m.first)){root=m.first;}}cout<<root<<endl;DFS(1,root,mp);// Use DFS to print out every child// Need to add depth for every vector arrayreturn0;}
Top comments (0)
Subscribe
We're a place where coders share, stay up-to-date and grow their careers.
Top comments (0)