pat（部分算法总结）

int pre[1010];
int (int root)
{
    int son,tmp;
    son = root;
    while(pre[root]!=root)
    {
        root=pre[root];
    }
    while(son!=root)  //路径压缩
    {
        tmp=pre[son];
        pre[son]=root;
        son =tmp;
    }
    return root;
}
int join(int a,int b)
{
    int x=union(a);
    int y=union(b);
    if(x!=y)
        pre[x]=y;
}



//dijkstra
void dijkstra(int x)
{
    fill(vis,vis+1025,0);
    fill(dis,dis+1025,0);
    vis[x]=1;
    for(int i=1;i<=n;i++)
    {
        dis[i]=maze[x][i];
    }
    for(int i=1;i<=n;i++)
    {
        int minn= inf;
        int idx=0;
        for(int j=1;j<=n;j++)
        {
            if(vis[i]==0&&dis[j]<minn)
            {
                minn=dis[j];
                idx=j;
            }
        }
        vis[idx]=1;
        for(int j=1;j<=n;j++)
        {
            if(!vis[j]&&dis[idx]+maze[idx][j]<dis[j])
                dis[j]=dis[idx]+maze[idx][j];
        }
    }
}


//二叉树

struct Node{

    int val;
    Node *left,*right;
    Node(int x):val(x),left(nullptr),right(nullptr)     {};

};
Node *root = nullptr;
Node *iinsert(Node *root,int val)
{
    if(root==nullptr)
        root=new Node(val);
    else if(root->val < val)
        root->right = iinsert(root->right,val);
    else
        root->left = iinsert(root->left, val);
}


//先序后序建立二叉树
void build(int prel,int prer,int postl,int postr)
{
    if(prel>=prer)
    {
        return ;
    }
    int val= preOrder[pre+1];
    int fa = prel;
    int postidx;
    for(int i=postl;i<=postr;i++)
        if(postOrder[i]==val)
            postidx= i;
    int num = postidx-postl;
    if(num==prer-prel-1)
        isUnique = false;
    node[fa].left = pre+1;
    build(prel+1,prel+num+1,postl,postidx);
    if(prer-prel-1>num)
    {
        node[fa].right = prel+num+2;
        build(prel+num+2,prer,postidx+1,postr-1);
    }
}

//先序中序建立二叉树
Node *build(int pl,int pr,int il,int ir)
{
    if(pl>pr)
        return NULL;
    Node *root = new Node(A[pl]);
    int idx;
    for(int i=il;i<=ir;i++)
    {
        if(A[pl]==B[i])
        {
            idx=i;
            break;
        }
    }
    root->left = build(pl+1,idx-il+pl,il,idx-1);
    root->right = build(idx-il+pl+1,pr,idx+1,ir);
    return root;
}


//中序后序建立二叉树
Node *build(int il,int ir,int postl,int postr)
{
    if(il>ir)
        return NULL;
    Node *root = new Node(B[postl]);
    int idx;
    for(int i=il;i<=ir;i++)
        if(A[i]==B[postl])
            idx= i,break;
    int t = idx-il;
    root->left = build(il,idx,postl+1,postl+t);
    root->right = build(idx+1,ir,postl+t+1,posr);
    return root;
}