L2-016. 愿天下有情人都是失散多年的兄妹
参考博客
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 using namespace std;
6 int flag;
7 struct node
8 {
9 int dad,mom,sex,bh;
10 node():dad(0),mom(0),sex(0),bh(-1){}
11 }peo[100005];
12 void mark(int x,int p,int cs)
13 {
14 if(cs==4||peo[x].dad==0)
15 return ;
16
17
18
19 if(peo[x].dad!=-1)
20 {
21 mark(peo[x].dad,p,cs+1);
22 peo[peo[x].dad].bh=p;
23 }
24 if(peo[x].mom!=-1)
25 {
26 peo[peo[x].mom].bh=p;
27 mark(peo[x].mom,p,cs+1);
28 }
29 }
30 void match(int x,int p,int cs)
31 {
32 if(cs==4||peo[x].dad==0||flag)
33 return ;
34
35 if(peo[x].dad!=-1)
36 { if(peo[peo[x].dad].bh==p)
37 flag=1;
38 else
39 match(peo[x].dad,p,cs+1);
40 }
41 if(peo[x].mom!=-1)
42 { if(peo[peo[x].mom].bh==p)
43 flag=1;
44 else
45 match(peo[x].mom,p,cs+1);
46 }
47
48 }
49 int main()
50 {
51 int n;
52 while(cin>>n)
53 {
54 int a,fa,ma;
55 char c;
56 for(int i=0;i<n;++i)
57 {
58 cin>>a>>c>>fa>>ma;
59
60 if(c=='M')
61 peo[a].sex=1;
62 else
63 peo[a].sex=0;
64
65 peo[a].dad=fa;
66 peo[a].mom=ma;
67
68 if(fa!=-1)
69 peo[fa].sex=1;
70 if(ma!=-1)
71 peo[ma].sex=0;
72 }
73
74 int m,x,y;
75 cin>>m;
76 for(int i=0;i<m;++i)
77 {
78 flag=0;
79 cin>>x>>y;
80 int j;
81 if(peo[x].sex==peo[y].sex)
82 cout<<"Never Mind"<<endl;
83 else
84 {
85 mark(x,i,0);
86 match(y,i,0);
87 if(flag)
88 cout<<"No"<<endl;
89 else
90 cout<<"Yes"<<endl;
91 }
92 }
93 }
94 }