基础并查集

上周六的时候吧，刷了几道并查集的题，学到了一些新东西，特此来记录下来方便以后复习
1.found函数新写法
以前我写并查集的found函数长这个样子：

int found(int x)
{
    if(f[x]==x)return x;
    return f[x]=found(f[x]);
}

这次在刷题的过程中看到了一种新鲜的写法如下：

int found(int x)
{
    int r=x;
    while(f[r]!=r)
    {
        r=f[r];
    }
    int j;
    while(x!=r)
    {
       j=f[x];
       f[x]=r;
       x=j;
     }
}

（收藏下来涨见识）
2.关于并查集和树的联系
无向图
树最重要的一个特点便是没有环，如何证明其没有环呢，就是要保证你每次合并的两个数的祖先都是不一样的。除此之外，比较容易忽略的一点便是不能有空树，即所有元素的祖先必须只能有一个

有向图
有向图除了要满足以上两个条件外，还有一点也十分重要，就是要保证方向。可能他们的祖先确实是一个，但有向图多了方向这个变量之后，可能造成其有两个根节点，所以需要加一个入度的判断

其中，我的s变量里存的是所有有入度的节点，如果最后我所有的节点和有入度的节点数之间差1，则代表其是树，程序正确。
（树的根节点只有出度没有入度）

做完题之后深刻感觉到自己涨知识了哈哈哈