首页 > 代码库 > 466E - Information Graph 巧妙的判断祖先于孩子的关系
466E - Information Graph 巧妙的判断祖先于孩子的关系
这题说的是给了一个公司员工100000 然后现在又3种操作第一种将y置为x的父亲，第二种操作将文件给第x个人签他签完给他的上司签，一直到没有上司为止，第三种操作问x是否签了第i份文件，然后 我们只要直到每两个点在最后形成的这颗树的位置只有祖先关系第一类 叔叔兄弟和其他的归为另一类，然后我们通过并查集判断他们是否在同一颗树中如果在判断他们的关系可以用刚刚处理出来的关系
处理这个关系用的是 访问的时间差可以判断是否为这个节点的孩子 看下面的代码 tin[x]<=tin[y]&&tou[x]>=tou[y] 那么y一定是x的孩子或者是x
#include <iostream>#include <cstdio>#include <string.h>#include <algorithm>#include <vector>using namespace std;const int maxn =100005;int tin[maxn],tou[maxn];int tag[maxn];vector<int>F[maxn];int op[maxn],x[maxn],y[maxn];int qusetion[maxn],time;vector<int>ansquestion[maxn];void dfs(int v, int p=-1){ tin[v]=time++; int L=F[v].size(); for(int i=0; i<L; ++i){ int to = F[v][i]; if(to==p) continue; dfs(to,v); } tou[v]=time++;}int per[maxn];int fa(int a){ return per[a]= a==per[a]?a:fa(per[a]);}void unin(int a, int b){ a=fa(a); b=fa(b); if(a!=b) per[a]=b;}bool ans[maxn];int paatt(int a,int b){ return tin[a]<=tin[b]&&tou[a]>=tou[b];}int main(){ memset(ans,false,sizeof(ans)); int n,m,number=0; scanf("%d%d",&n,&m); for(int i=0; i<m; ++i){ scanf("%d",&op[i]); if(op[i]==2){ scanf("%d",&x[i]); }else scanf("%d%d",&x[i],&y[i]); if(op[i]==1){ F[y[i]].push_back(x[i]); tag[x[i]]++; }else if(op[i]==2){ qusetion[i]=++number; }else { ansquestion[y[i]].push_back(i); } } time=1; for(int i=1; i<=n; ++i){ if(tag[i]!=0||tin[i]!=0) continue; dfs(i); } for(int i=1; i<=n; ++i) per[i]=i; for(int i=0; i<m; ++i){ if(op[i]==1){ unin(x[i],y[i]); }else if(op[i]==2){ int an= qusetion[i]; int root=x[i]; int L = ansquestion[an].size(); for(int j=0; j<L; ++j){ int to = ansquestion[an][j]; int in=x[to]; ans[to]=fa(in)==fa(root)&&paatt(in,root); } } } for(int i=0; i<m; ++i) if(op[i]==3) printf("%s\n",ans[i]?"YES":"NO"); return 0;}
466E - Information Graph 巧妙的判断祖先于孩子的关系
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。