首页 » C++ » 天梯赛 愿天下有情人都是失散多年的兄妹(DFS)

天梯赛 愿天下有情人都是失散多年的兄妹(DFS)

原文 http://blog.csdn.net/Link_Ray/article/details/79189266

2018-01-29 02:00:45阅读(219)

一开始做的时候一直卡在17分,怎么看都觉得没有问题,最后看了别人博客才知道,竟然还会询问某人的父母和其他人的父母可否结婚(当然是选择原谅TA啦)。。。。像我这样纯洁的小孩子根本就考虑不到啊。。。
所以,在输入父母的序号时也需将性别标记上。

题目说要保证5代之间没有血缘关系,那么可以先找其中一人的5代并都进行标记,再找第二个人的5代,若第二个人的5代中有已经被标记的,那么说明他们不可以结婚。

此题的抽象模型类似于一颗二叉树。

#include <cstring>
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <set>
using namespace std;
struct peo{
    int id; char sex;
}peo[10011];
int fpre[10015], mpre[10015];
int vis1[10015];
bool flag = true;
void DFS(int f1,int m1,int cnt){
    if(cnt >= 5) return;
    if(!flag) return; // 存在血缘关系就退出
    if(f1 != -1){
        if(vis1[f1] == 1)
            flag = false;
        vis1[f1] = 1;
    }
    if(m1 != -1){
        if(vis1[m1] == 1)
            flag = false;
        vis1[m1] = 1;
    }
    if(f1 != -1) 
        dfs(fpre[f1], mpre[f1],cnt+1); // 父亲的父母
    if(m1 != -1)
        dfs(fpre[m1], mpre[m1],cnt+1); // 母亲的父母
}
int main(){
    int n; cin >> n;
    memset(fpre,-1,sizeof(fpre)); memset(mpre,-1,sizeof(mpre));
    for(int i = 0; i < n; ++i){
        int id; char sex; int f,m;
        cin >> id >> sex >> f >> m;
        peo[id].id = id; peo[id].sex = sex;
        fpre[id] = f; mpre[id] = m; // 父亲和母亲的序号
        peo[f].id = f; peo[f].sex = 'M'; // 写入父母的信息
        peo[m].id = m; peo[m].sex = 'F';
    }
    int ask;
    cin >> ask;
    while(ask--){
        int id1,id2; cin >> id1 >> id2;
        if(peo[id1].sex == peo[id2].sex){ // 本人也算作一代
            cout <<"Never Mind" << endl; continue;
        }
        flag = true;
        memset(vis1,0,sizeof(vis1)); 
        int f1 = fpre[id1], m1 = mpre[id1];
        int f2 = fpre[id2], m2 = mpre[id2];
        dfs(f1,m1,1); // 除去本人这一代,所以从1开始
        dfs(f2,m2,1);
        if(flag)
            cout <<"Yes" << endl;
        else
            cout <<"No" << endl;
    }
    return 0;
}

最新发布

CentOS专题

关于本站

5ibc.net旗下博客站精品博文小部分原创、大部分从互联网收集整理。尊重作者版权、传播精品博文,让更多编程爱好者知晓!

小提示

按 Ctrl+D 键,
把本文加入收藏夹