判断无向图是否有环路的方法 -并查集

转载：https://blog.csdn.net/xyt8023y/article/details/46312499
并查集来判断是否有环路。
首先初始化所有元素的根为-1，-1代表根节点，接下来对于图中的每一条边(v1,v2)都并入集合，并入的方式为查找v1和v2的根节点，然后让v2的根节点作为v1的根节点，查找根节点的过程为：如果当前的结点根为-1，说明这个结点就是根，直接返回，否则再继续查找结点父亲的根，直到找到祖先结点。

int findroot(int x) {
    return fa[x] == -1 ? x : fa[x]=findroot(fa[x]);    
}

找到v1的根root1和v2的根root2以后，首先判断它们是否相同？对于一个无环图，某条边并入集合前是不会出现两个点同根的情况的，原因也很简单，因为这条边中至少有一个点是新加入这个集合的(否则就有重边了)，这个新加入的点的root要么为-1要么为其他的结点，只有图有环的时候，才会出现两个点的根相同相同，说明有环。