#include <iostream> #include<vector> #include<string> #include<sstream> #include<unordered_map> #include<algorithm> #include<set> using namespace std; //表示图中的节点, //把图建出来, struct node { // type = 1是class,type=2是实例 int type; string s; vector<node*>next; //代表下一个节点, node(int t,string s1) :type(t),s(s1),next(0){} }; vector<string>res; void dfs(node* begin) { if (!begin) return;//已经到达最后了 for (node* next : begin->next) //遍历所有的边 { if (next->type == 1) { res.push_back(next->s); } dfs(next); } } int main() { unordered_map<string, node*>occur;//根据string映射点,防止重复建点 int n; cin >> n;//一共有n条边 string s1; string find; int i = -1; //首先读出n对关系 while (getline(cin, s1)) { stringstream ss(s1); string str; vector<string>strs; i++; if (i == n + 1) { find = s1; break; } while (getline(ss, str, ' ')) { if (i > 0) strs.push_back(str); //获取到一个三元组关系,开始建立点或边 } /*起点、终点、关系*/ if (strs.size() == 3) { string end = strs[0], begin = strs[2], relate = strs[1]; node* a = nullptr; if (!occur.count(end)) //如果没有该节点则新建一个 { if (relate[0] == 'i') //这是概念-实例联系 a = new node(1, end); else a = new node(2, end);//这是概念-子概念联系 occur[end] = a; } else a = occur[end];//a是终点 //同样构造起点 node* b = nullptr; if (!occur.count(begin)) { b = new node(1, begin);//建立起点 occur[begin] = b; } else b = occur[begin];//如果已经有了直接读出来 b->next.push_back(a);//建立 b->a 边的联系 } } node* b = occur[find]; // 已经找到了find节点,然后开始根据find为起点开始dfs dfs(b); if (res.empty()) { cout << "empty"; return 0; } set<string>tmp; for (auto ele : res) tmp.emplace(ele); res.clear(); for (auto ele : tmp) res.push_back(ele); sort(res.begin(), res.end()); for (auto s : res) { cout << s << " "; } return 0; }
全部评论
(6) 回帖