首页 > 华为9.1机试第二题,构造图DFS想不通为什么过25%
头像
合工大ssf
发布于 2021-09-01 21:06
+ 关注

华为9.1机试第二题,构造图DFS想不通为什么过25%

#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) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

近期精华帖

热门推荐