代码随想录 (programmercarl.com)
寻找图中是否存在路径这道题中的类可看做并查集的标准类
目录
1971.寻找图中是否存在路径
684.冗余连接
685.冗余连接II
1971.寻找图中是否存在路径
1971. 寻找图中是否存在路径
已解答
简单
相关标签
相关企业
有一个具有 n
个顶点的 双向 图,其中每个顶点标记从 0
到 n - 1
(包含 0
和 n - 1
)。图中的边用一个二维整数数组 edges
表示,其中 edges[i] = [ui, vi]
表示顶点 ui
和顶点 vi
之间的双向边。 每个顶点对由 最多一条 边连接,并且没有顶点存在与自身相连的边。
请你确定是否存在从顶点 source
开始,到顶点 destination
结束的 有效路径 。
给你数组 edges
和整数 n
、source
和 destination
,如果从 source
到 destination
存在 有效路径 ,则返回 true
,否则返回 false
。
示例 1:
输入:n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2 输出:true 解释:存在由顶点 0 到顶点 2 的路径: - 0 → 1 → 2 - 0 → 2
示例 2:
输入:n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5 输出:false 解释:不存在由顶点 0 到顶点 5 的路径.
提示:
1 <= n <= 2 * 105
0 <= edges.length <= 2 * 105
edges[i].length == 2
0 <= ui, vi <= n - 1
ui != vi
0 <= source, destination <= n - 1
- 不存在重复边
- 不存在指向顶点自身的边
class Solution {
int[] father; // 存储每个节点的父节点指针数组
// 判断是否存在从源节点到目标节点的有效路径
public boolean validPath(int n, int[][] edges, int source, int destination) {
father = new int[n]; // 初始化父节点数组
init(); // 初始化并查集数据结构
// 合并通过边连接的顶点
for (int i = 0; i < edges.length; i++) {
join(edges[i][0], edges[i][1]); // 合并顶点
}
// 检查源节点和目标节点是否属于同一个连通分量
return isSame(source, destination);
}
// 初始化并查集数据结构
public void init() {
for (int i = 0; i < father.length; i++) {
father[i] = i; // 每个顶点最初都是自己的父节点
}
}
// 查找包含顶点 u 的连通分量的根节点
public int find(int u) {
if (u == father[u]) {
return u; // 如果 u 是自己的父节点,则它就是根节点
} else {
father[u] = find(father[u]); // 路径压缩:更新 u 的父节点为根节点
return father[u]; // 返回根节点
}
}
// 检查顶点 u 和 v 是否属于同一个连通分量
public boolean isSame(int u, int v) {
u = find(u); // 查找 u 的根节点
v = find(v); // 查找 v 的根节点
return u == v; // 如果 u 和 v 具有相同的根节点(即它们属于同一个连通分量),则返回 true
}
// 合并包含顶点 u 和 v 的连通分量
public void join(int u, int v) {
u = find(u); // 查找 u 的根节点
v = find(v); // 查找 v 的根节点
if (u == v) return; // 如果 u 和 v 已经属于同一个连通分量,则直接返回
father[v] = u; // 将 v 的根节点的父节点设置为 u 的根节点,实际上是合并了两个连通分量
}
}
684.冗余连接
684. 冗余连接
中等
树可以看成是一个连通且 无环 的 无向 图。
给定往一棵 n
个节点 (节点值 1~n
) 的树中添加一条边后的图。添加的边的两个顶点包含在 1
到 n
中间,且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n
的二维数组 edges
,edges[i] = [ai, bi]
表示图中在 ai
和 bi
之间存在一条边。
请找出一条可以删去的边,删除后可使得剩余部分是一个有着 n
个节点的树。如果有多个答案,则返回数组 edges
中最后出现的那个。
示例 1:
输入: edges = [[1,2], [1,3], [2,3]] 输出: [2,3]
示例 2:
输入: edges = [[1,2], [2,3], [3,4], [1,4], [1,5]] 输出: [1,4]
提示:
n == edges.length
3 <= n <= 1000
edges[i].length == 2
1 <= ai < bi <= edges.length
ai != bi
-
edges
中无重复元素 - 给定的图是连通的
class Solution {
private int n; // 节点数量,范围从 3 到 1000
private int[] father; // 存储并查集的父节点信息
// 初始化并查集
public void init() {
n = 1005; // 设置节点数量上限为 1005(包含 1000 个节点)
father = new int[n]; // 初始化父节点数组
// 并查集初始化
for (int i = 0; i < n; ++i) {
father[i] = i; // 每个节点初始时都指向自己
}
}
// 寻找并查集中节点 u 的根节点
private int find(int u) {
if(u == father[u]) { // 如果节点 u 是自己的父节点,则它就是根节点
return u;
}
father[u] = find(father[u]); // 路径压缩:将节点 u 沿着路径直接连接到根节点
return father[u]; // 返回根节点
}
// 将节点 v->u 这条边加入并查集
private void join(int u, int v) {
u = find(u); // 查找节点 u 的根节点
v = find(v); // 查找节点 v 的根节点
if (u == v) return ; // 如果节点 u 和节点 v 已经在同一个集合中,则不进行合并
father[v] = u; // 将节点 v 的根节点连接到节点 u 的根节点上,实现合并
}
// 判断节点 u 和节点 v 是否位于同一个连通分量中
private Boolean same(int u, int v) {
u = find(u); // 查找节点 u 的根节点
v = find(v); // 查找节点 v 的根节点
return u == v; // 如果两个节点具有相同的根节点,则它们在同一个连通分量中
}
// 寻找冗余连接,即找到使图中出现环的最后一条边
public int[] findRedundantConnection(int[][] edges) {
init(); // 初始化并查集
for (int i = 0; i < edges.length; i++) {
if (same(edges[i][0], edges[i][1])) { // 如果两个节点已经在同一个集合中,说明加入该边会形成环
return edges[i]; // 返回造成环的边
} else {
join(edges[i][0], edges[i][1]); // 否则,将当前边加入并查集
}
}
return null; // 如果没有找到冗余连接,则返回空
}
}
685.冗余连接II
685. 冗余连接 II
困难
在本问题中,有根树指满足以下条件的 有向 图。该树只有一个根节点,所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点,而根节点没有父节点。
输入一个有向图,该图由一个有着 n
个节点(节点值不重复,从 1
到 n
)的树及一条附加的有向边构成。附加的边包含在 1
到 n
中的两个不同顶点间,这条附加的边不属于树中已存在的边。
结果图是一个以边组成的二维数组 edges
。 每个元素是一对 [ui, vi]
,用以表示 有向 图中连接顶点 ui
和顶点 vi
的边,其中 ui
是 vi
的一个父节点。
返回一条能删除的边,使得剩下的图是有 n
个节点的有根树。若有多个答案,返回最后出现在给定二维数组的答案。
示例 1:
输入:edges = [[1,2],[1,3],[2,3]] 输出:[2,3]
示例 2:
输入:edges = [[1,2],[2,3],[3,4],[4,1],[1,5]] 输出:[4,1]
提示:
n == edges.length
3 <= n <= 1000
edges[i].length == 2
1 <= ui, vi <= n
class Solution {
private static final int N = 1010; // 如题:二维数组大小的在3到1000范围内
private int[] father;
public Solution() {
father = new int[N];
// 并查集初始化
for (int i = 0; i < N; ++i) {
father[i] = i;
}
}
// 并查集里寻根的过程
private int find(int u) {
if(u == father[u]) {
return u;
}
father[u] = find(father[u]);
return father[u];
}
// 将v->u 这条边加入并查集
private void join(int u, int v) {
u = find(u);
v = find(v);
if (u == v) return ;
father[v] = u;
}
// 判断 u 和 v是否找到同一个根,本题用不上
private Boolean same(int u, int v) {
u = find(u);
v = find(v);
return u == v;
}
/**
* 初始化并查集
*/
private void initFather() {
// 并查集初始化
for (int i = 0; i < N; ++i) {
father[i] = i;
}
}
/**
* 在有向图里找到删除的那条边,使其变成树
* @param edges
* @return 要删除的边
*/
private int[] getRemoveEdge(int[][] edges) {
initFather();
for(int i = 0; i < edges.length; i++) {
if(same(edges[i][0], edges[i][1])) { // 构成有向环了,就是要删除的边
return edges[i];
}
join(edges[i][0], edges[i][1]);
}
return null;
}
/**
* 删一条边之后判断是不是树
* @param edges
* @param deleteEdge 要删除的边
* @return true: 是树, false: 不是树
*/
private Boolean isTreeAfterRemoveEdge(int[][] edges, int deleteEdge)
{
initFather();
for(int i = 0; i < edges.length; i++)
{
if(i == deleteEdge) continue;
if(same(edges[i][0], edges[i][1])) { // 构成有向环了,一定不是树
return false;
}
join(edges[i][0], edges[i][1]);
}
return true;
}
public int[] findRedundantDirectedConnection(int[][] edges) {
int[] inDegree = new int[N];
for(int i = 0; i < edges.length; i++)
{
// 入度
inDegree[ edges[i][1] ] += 1;
}
// 找入度为2的节点所对应的边,注意要倒序,因为优先返回最后出现在二维数组中的答案
ArrayList<Integer> twoDegree = new ArrayList<Integer>();
for(int i = edges.length - 1; i >= 0; i--)
{
if(inDegree[edges[i][1]] == 2) {
twoDegree.add(i);
}
}
// 处理图中情况1 和 情况2
// 如果有入度为2的节点,那么一定是两条边里删一个,看删哪个可以构成树
if(!twoDegree.isEmpty())
{
if(isTreeAfterRemoveEdge(edges, twoDegree.get(0))) {
return edges[ twoDegree.get(0)];
}
return edges[ twoDegree.get(1)];
}
// 明确没有入度为2的情况,那么一定有有向环,找到构成环的边返回就可以了
return getRemoveEdge(edges);
}
}