get到新知识，心情愉悦。
先看先序排列
P1030 [NOIP2001 普及组] 求先序排列https://www.luogu.com.cn/problem/P1030题目描述
给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，且二叉树的节点个数 ≤8）。
输入格式
共两行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。
输出格式
共一行一个字符串，表示一棵二叉树的先序。
输入输出样例
输入 #1复制
BADC
BDCA输出 #1复制
ABCD【题目来源】
NOIP 2001 普及组第三题
思路：在草稿纸上多次手工遍历，找出由中后序排列->先序排列的规律，先从后序最后一个字母（这就是根）开始A，在中序知道对应的字母，将中序分成俩部分，依据中序的俩部分，将后序分成俩部分，左边一部分是A的左子树，右边一部分是A的右子树。以此类推。。。先序为根左右，所以先把根输出，然后递归左半然后右半。
代码实现：
#includeusing namespace std;
void DLR(char *m,char *b,int l,int r,int i,int j)
{
if(i==j)
{
printf("%c",b[j]);
return;
}
for(int k=l;k<=r;k++)
{
if(m[k]==b[j])
{
printf("%c",b[j]);
if(k-1>=l) DLR(m,b,l,k-1,i,i+(k-1-l));
if(k+1<=r) DLR(m,b,k+1,r,j+k-r,j-1);
break;
}
}
}
int main()
{
char m[30];
char b[30];
cin>>m>>b;
int len=strlen(m);
DLR(m,b,0,len-1,0,len-1);
return 0;
}
//ABEDFCHG
//AEFDBHGC 新知识:并查集P3367 【模板】并查集https://www.luogu.com.cn/problem/P3367
并查集，合并与查询，是一种树结构。原来判断两个对象之间的关系，有关系和没关系。无法得出具体关系。
通过数组parent[x]=x_father来模拟两个元素之间的结点与孩子的关系，x的结点是x_father。
比如如果要合并1和2所在的集合，就要把1和2所在的那棵树的根找出来（find），然后将一个根接在(connect)另一个根上面，一个为结点，一个为子树。
题目描述
如题，现在有一个并查集，你需要完成合并和查询操作。
输入格式第一行包含两个整数N,M ,表示共有 N 个元素和 M 个操作。
接下来 MM 行，每行包含三个整数 Zi,Xi,Yi 。
当 Zi=1 时，将Xi 与Yi 所在的集合合并。
当 Zi=2 时，输出 Xi 与Yi 是否在同一集合内，是的输出 Y；否则输出 N。
对于每一个 Zi=2 的操作，都有一行输出，每行包含一个大写字母，为 Y或者 N。
输入 #1复制
4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4输出 #1复制
N
Y
N
Y对于30% 的数据，N≤10，M≤20。
对于 70% 的数据，N≤100，M≤103。
对于 100% 的数据，1≤N≤104，1≤M≤2×105，1≤Xi,Yi≤N，Zi∈{1,2}。
代码实现：
#includeusing namespace std;
int find_root(int x,int *parent)
{
int x_root=x;
while(parent[x_root]!=0)
{
x_root=parent[x_root];
}
return x_root;
}
int connect(int x,int y,int *parent)
{
int x_root=find_root(x,parent);
int y_root=find_root(y,parent);
if(x_root==y_root)
{
return 0;
}
else
{
parent[x_root]=y_root;
return 1;
}
}
int main()
{
int parent[10000+5]={0};
int Z,M,N;
cin>>N>>M;
int x,y;
while(M--)
{
cin>>Z>>x>>y;
if(Z==1) connect(x,y,parent);
else
{
if(find_root(x,parent)==find_root(y,parent)&&find_root(x,parent)!=0)
{
printf("Y\n");
}
else
{
printf("N\n");
}
}
}
return 0;
} 由于这里在合并的时候总是，左边那个集合连上右边那个集合，会导致树的深度过长，在find的时候会花费额外的时间，以至于提交结果时间超限
所以要将深度小的接在深度长的上面，就需要多定义一个数组deep 来存储深度
#includeusing namespace std;
int find_root(int x,int *parent)
{
int x_root=x;
while(parent[x_root]!=0)
{
x_root=parent[x_root];
}
return x_root;
}
int connect(int x,int y,int *parent,int *deep)
{
int x_root=find_root(x,parent);
int y_root=find_root(y,parent);
if(x_root==y_root)
{
return 0;
}
else
{
if(deep[x_root]>deep[y_root])
{
parent[y_root]=x_root;
}
else if(deep[y_root]>deep[x_root])
{
parent[x_root]=y_root;
}
else
{
parent[y_root]=x_root;
deep[x_root]++;
}
return 1;
}
}
int main()
{
int parent[10000+5]={0};
int deep[10000+5]={0};
int Z,M,N;
cin>>N>>M;
int x,y;
while(M--)
{
cin>>Z>>x>>y;
if(Z==1) connect(x,y,parent,deep);
else
{
if(find_root(x,parent)==find_root(y,parent)&&find_root(x,parent)!=0)
{
printf("Y\n");
}
else
{
printf("N\n");
}
}
}
return 0;
} AC，不过谁能告诉我这个N有什么用？？？？满脸疑惑
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
