解决的问题

查找图是否成环

理解过程

思想

右边图代表着圈里面的点是连通的
成环的标志是：圈内某两元素之间还有一条边

转化为代码（合并两个圈）

利用数组建树，数组元素值代表该位置的父亲结点，-1代表为独立结点

因此：
合并两圈=把a2图的头结点的父亲结点改为a1图的头结点

当发现某条边的两个结点的根节点是同一结点时，代表着成环了

代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define VERTICES 6
void initialise(int parent[])
{
    int i;
    for(i=0;i<VERTICES;i++)
    {
        parent[i]=-1;
    }
}
int find_root(int x,int parent[])
{
    int x_root=x;
    while(parent[x_root]!=-1)
    {
        x_root = parent[x_root];
    }
    return x_root;

}

//如果返回为1，代表union成功，
//返回0时合并失败（两点在同一的区域）
 int  union_vertices(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[VERTICES] = {0};
    int edges[6][2]={
        {0,1},{1,2},{1,3},
        {2,4},{3,4},{2,5}
    };
    initialise(parent);
    int i;
    for(i=0;i<6;i++)
    {
        int x = edges[i][0];
        int y = edges[i][1];
        if(union_vertices(x,y,parent)==0)
        {
            cout<<"YES"<<endl;
            return 0;
        }
    }
    return 0;
}

问题

可能会出先这种情况，复杂度变为O（n）

算法优化：压缩路径

想法：

用Rank记录树的高度，
if （rank[x]> rank[y]）
则 ：y树拼到x树
且新rank=rank[x]；

代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define VERTICES 6
void initialise(int parent[],int rank[])
{
    int i;
    for(i=0;i<VERTICES;i++)
    {
        parent[i]=-1;
        rank[i]=0;
    }
}

int find_root(int x,int parent[])
{
    int x_root=x;
    while(parent[x_root]!=-1)
    {
        x_root = parent[x_root];
    }
    return x_root;

}

//如果返回为1，代表union成功，
//返回0时合并失败（两点在同一的区域）
 int  union_vertices(int x,int y,int parent[],int rank[])
 {
     int x_root= find_root(x,parent);
     int y_root = find_root(y,parent);
     if(x_root==y_root) return 0;
     else
     {
         if(rank[x_root]>rank[y_root])
         {
               parent[y_root]=x_root;
         }
         else  if(rank[x_root]<rank[y_root])
         {
             parent[x_root]=y_root;
         }
         else if(rank[x_root]==rank[y_root])
         {
              parent[x_root]=y_root;
              rank[y_root]++;
         }
         return 1;
     }
 }

int main()
{
    int parent[VERTICES] = {0};
    int rank[VERTICES] = {0};
    int edges[6][2]={
        {0,1},{1,2},{1,3},
        {2,4},{3,4},{2,5}
    };
    initialise(parent,rank);
    int i;
    for(i=0;i<6;i++)
    {
        int x = edges[i][0];
        int y = edges[i][1];
        if(union_vertices(x,y,parent,rank)==0)
        {
            cout<<"YES"<<endl;
            return 0;
        }
    }
    return 0;
}