贝壳2018.9.3笔试题之家族关系

思路：时间紧张什么图啊树啊都觉得不好实现用map最简单了把所有已知的信息先存入map 存入的时候（1）确定根谁和根比较都是根的孩子（2）兄弟关系，如果a b 的祖先相同，那么肯定是兄弟（3）祖先关系可能不是直系需要while循环判断（4）如果都判断完毕不是祖先，那么肯定是没关系

代码如下：ac38% 不知道哪种自己没考虑到~欢迎大佬指出！

#include<iostream>
#include<map>
using namespace std;
int main()
{
    int n;
    cin>>n;
    map<int,int>zupu;
    int root=0;
    for(int i=0;i<n;i++)
    {
        int a,b;
        cin>>a>>b;
        pair<int,int>value(a,b);
        zupu.insert(value);
        if(zupu[a]==-1)
            root=a;
    }
    int m;
    cin>>m;
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        if(a==root||zupu[b]==a)
        {
            cout<<"1"<<endl;
        }
        else if(b==root||zupu[a]==b)
        {
            cout<<"2"<<endl;
        }
        else if(zupu[a]==zupu[b])
        {
            cout<<"0"<<endl;
        }
        else
        {
            bool flag=true;
            int tmp1;
            while(zupu.find(zupu[b])!=zupu.end())
            {
                tmp1=zupu[b];
                if(zupu[tmp1]==a)
                {
                    cout<<"1"<<endl;
                    flag=false;
                    break;
                }
                b=tmp1;
            }
            int tmp;
            while(flag&&zupu.find(zupu[b])!=zupu.end())
            {
                tmp=zupu[b];
                if(zupu[tmp]==a)
                {
                    cout<<"1"<<endl;
                    flag=false;
                    break;
                }
                b=tmp;
            }
            if(flag)
                cout<<"0"<<endl;
        }
    }
    return 0;
}

#贝壳找房#

全部评论

推荐最新楼层

3面试，1个offer

河南工业大学 C++

#include<iostream> #include<vector> #include<stack> #include<queue> #include<unordered_map> #include<string> #include<map> #include<cstring> #include<algorithm> using namespace std; int main() { int n; cin>>n; map<int,int> m; for(int i=0;i<n;i++) { int a,b; cin>>a>>b; m[a]=b; } int qn; cin>>qn; vector<int> fir; vector<int> sec; for(int i=0;i<qn;i++) { int aa,bb; cin>>aa>>bb; fir.push_back(aa); sec.push_back(bb); } vector<int> ans; for(int i=0;i<qn;i++) { bool flag1=false; bool flag2=false; if(m.find(fir[i])==m.end()&&m.find(sec[i])==m.end()) { ans.push_back(0); break; } int temp=fir[i]; while(m.find(temp)!=m.end()) { if(m[temp]==sec[i]) { flag1=true; ans.push_back(2); break; } else { temp=m[temp]; } } int temp2=sec[i]; while(m.find(temp2)!=m.end()) { if(m[temp2]==fir[i]) { flag2=true; ans.push_back(1); break; } else { temp2=m[temp2]; } } if(!flag1&&!flag2) ans.push_back(0); } int size2=ans.size(); for(int i=0;i<size2;i++) { cout<<ans[i]<<endl; } return 0; }

点赞回复分享

发布于 2018-09-05 10:27

3面试，1个offer

河南工业大学 C++

用的map ac了

点赞回复分享

发布于 2018-09-04 11:33