被gydalao从搜索拉回二叉树后也算是搞了5,6天吧。。不算多也不算少，题也是能敲则敲，基本都是看着模板，刷着题解，好赖都懂了，但是教材上求二叉树的直径和并查集我是服，大概我太弱，或是没有耐心，感觉一眼不可学的样子，决定不如先放放，先学搜索。
某Lcenturydalao的递归式
tree(i-la,la,lb-n-la+i);
tree(n+la-i-1,i+1,lb-1);
不用数字转
#include <iostream>
using namespace std;
string a,b;
inline void tree(int n,int la,int lb)
{
if(n<=0) return;
for(int i=la;i<=la+n-1;i++)
{
if(a[i]==b[lb])
{
cout<<b[lb];
tree(i-la,la,lb-n-la+i);
tree(n+la-i-1,i+1,lb-1);
return ;
}
}
}
int main()
{
cin>>a;
cin>>b;
tree(a.size(),0,a.size()-1);
return 0;
}
用数字转
#include <iostream>
using namespace std;
string a,b;
int zz[1000086],hh[1000086];
int len1=0,len2=0,top;
inline void tree(int n,int la,int lb)
{
if(n<=0) return;
for(int i=la;i<=la+n-1;i++)
{
if(zz[i]==hh[lb])
{
cout<<char(hh[lb]+64);
tree(i-la,la,lb-n-la+i);
tree(n+la-i-1,i+1,lb-1);
return ;
}
}
}
int main()
{
cin>>a;
cin>>b;
for(int i=0;i<a.size();i++)
zz[++len1]=int(a[i]-'A'+1);
for(int i=0;i<b.size();i++)
hh[++len2]=int(b[i]-'A'+1);
tree(a.size(),1,a.size());
return 0;
}
//并查集jb题，亲戚
#include <bits/stdc++.h>
#define N 100086
using namespace std;
int dad[N];
int n,m,p;
inline void initial()//并查集初始化
{
for(int i=1;i<=n;i++)
dad[i]=i;
}
inline int getfather(int x)//查找
{
if(dad[x]==x) return x;
else
{
dad[x]=getfather(dad[x]);
return dad[x];
}
}
inline void hb(int s,int d)//合并
{
s=getfather(s);
d=getfather(d);
if(s==d) return;
dad[d]=s;
}
inline bool findfather(int x,int y)//判断是否属于同一集合，即根节点是否相同
{
int fx,fy;
fx=getfather(x);
fy=getfather(y);
return (fx==fy);
}
int main()
{
cin>>n>>m>>p;
initial();
int x,y;
for(int i=1;i<=m;i++)
{
cin>>x>>y;
hb(x,y);
}
int g,h;
for(int i=1;i<=p;i++)
{
cin>>g>>h;
if(findfather(g,h))
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
return 0;
}
//给自己的提醒，
并查集：
1）将两个元素合并到同一集合：
两个节点在同一集合，其实就是两个节点的根节点在同一个集合，先找到这两个集合的根节点，如果根节点相同，就return 否则就把两个根节点相连
2）判断两个元素是否在同一集合
找两个元素的根节点，根节点相同，就在同一集合，反之不在