1. 判断环路,并查集祖先节点的实现

力扣官方题解参考,更加通用的简单图论解法

class Solution {
public int[] findRedundantDirectedConnection(int[][] edges)
{
int n=edges.length;
int[] parent=new int[n+1];
Operate ances=
new Operate(n+1);
int conflict=-1;
int cycle=-1;
for(int i=0;i<n+1;i++)
parent[i]=i;
for(int i=0;i<n;i++)
{
int x=edges[i][0];
int y=edges[i][1];
if(y!=parent[y])
{
conflict=i;
//不链接
}
else//不冲突,可以连接
{
parent[y]=x;
if(ances.find(x)==ances.find(y))//用祖先数组判断回路
{
cycle=i;
}
else
{
ances.union(x,y);
}
}
}
if(conflict<0)//无冲突,则为回路
{
return new int[]{edges[cycle][0],edges[cycle][1]};
}
else
{//有冲突,判断有无回路
int[] nodes=edges[conflict];
if(cycle<0)
return nodes;
else
return new int[]{parent[nodes[1]],nodes[1]};
}
}

}


class Operate//并查集祖先数组模板,可以再加一个parent[]表示父节点
{
int[] ancestor;//祖先数组
Operate(
int n)
{
ancestor=
new int[n];
for(int i=0;i<n;i++)
ancestor[i]=i;
}
int find(int index)//
{
if(ancestor[index]!=index)
ancestor[index]=find(ancestor[index]);
return ancestor[index];//递归更新并查询祖先数组
}
void union(int index1,int index2)
{
ancestor[find(index2)]=find(index1);//index2归并至index1
}
}