427 lines
9.2 KiB
Markdown
427 lines
9.2 KiB
Markdown
|
||
<p align="center"><strong><a href="./qita/join.md">参与本项目</a>，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们受益！</strong></p>
|
||
|
||
# 107. 寻找存在的路径
|
||
|
||
[卡码网题目链接（ACM模式）](https://kamacoder.com/problempage.php?pid=1179)
|
||
|
||
题目描述
|
||
|
||
给定一个包含 n 个节点的无向图中，节点编号从 1 到 n （含 1 和 n ）。
|
||
|
||
你的任务是判断是否有一条从节点 source 出发到节点 destination 的路径存在。
|
||
|
||
输入描述
|
||
|
||
第一行包含两个正整数 N 和 M，N 代表节点的个数，M 代表边的个数。
|
||
|
||
后续 M 行，每行两个正整数 s 和 t，代表从节点 s 与节点 t 之间有一条边。
|
||
|
||
最后一行包含两个正整数，代表起始节点 source 和目标节点 destination。
|
||
|
||
输出描述
|
||
|
||
输出一个整数，代表是否存在从节点 source 到节点 destination 的路径。如果存在，输出 1；否则，输出 0。
|
||
|
||
输入示例
|
||
|
||
```
|
||
5 4
|
||
1 2
|
||
1 3
|
||
2 4
|
||
3 4
|
||
1 4
|
||
```
|
||
|
||
输出示例
|
||
|
||
1
|
||
|
||
提示信息
|
||
|
||
|
||
|
||
数据范围：
|
||
|
||
1 <= M, N <= 100。
|
||
|
||
## 思路
|
||
|
||
**[《代码随想录》算法视频公开课](https://programmercarl.com/other/gongkaike.html)：[图论：没想到并查集这么简单 ！](https://www.bilibili.com/video/BV1k3T7zWEVj),相信结合视频再看本篇题解，更有助于大家对本题的理解**。
|
||
|
||
本题是并查集基础题目。 如果还不了解并查集，可以看这里：[并查集理论基础](https://programmercarl.com/kamacoder/图论并查集理论基础.html)
|
||
|
||
并查集可以解决什么问题呢？
|
||
|
||
主要就是集合问题，**两个节点在不在一个集合，也可以将两个节点添加到一个集合中**。
|
||
|
||
这里整理出我的并查集模板如下：
|
||
|
||
```CPP
|
||
int n = 1005; // n根据题目中节点数量而定，一般比节点数量大一点就好
|
||
vector<int> father = vector<int> (n, 0); // C++里的一种数组结构
|
||
|
||
// 并查集初始化
|
||
void init() {
|
||
for (int i = 0; i < n; ++i) {
|
||
father[i] = i;
|
||
}
|
||
}
|
||
// 并查集里寻根的过程
|
||
int find(int u) {
|
||
return u == father[u] ? u : father[u] = find(father[u]); // 路径压缩
|
||
}
|
||
|
||
// 判断 u 和 v是否找到同一个根
|
||
bool isSame(int u, int v) {
|
||
u = find(u);
|
||
v = find(v);
|
||
return u == v;
|
||
}
|
||
|
||
// 将v->u 这条边加入并查集
|
||
void join(int u, int v) {
|
||
u = find(u); // 寻找u的根
|
||
v = find(v); // 寻找v的根
|
||
if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
|
||
father[v] = u;
|
||
}
|
||
```
|
||
|
||
以上模板中，只要修改 n 大小就可以。
|
||
|
||
并查集主要有三个功能：
|
||
|
||
1. 寻找根节点，函数：find(int u)，也就是判断这个节点的祖先节点是哪个
|
||
2. 将两个节点接入到同一个集合，函数：join(int u, int v)，将两个节点连在同一个根节点上
|
||
3. 判断两个节点是否在同一个集合，函数：isSame(int u, int v)，就是判断两个节点是不是同一个根节点
|
||
|
||
简单介绍并查集之后，我们再来看一下这道题目。
|
||
|
||
为什么说这道题目是并查集基础题目，题目中各个点是双向图链接，那么判断 一个顶点到另一个顶点有没有有效路径其实就是看这两个顶点是否在同一个集合里。
|
||
|
||
如何算是同一个集合呢，有边连在一起，就算是一个集合。
|
||
|
||
此时我们就可以直接套用并查集模板。
|
||
|
||
使用 join(int u, int v)将每条边加入到并查集。
|
||
|
||
最后 isSame(int u, int v) 判断是否是同一个根 就可以了。
|
||
|
||
C++代码如下：
|
||
|
||
```CPP
|
||
#include <iostream>
|
||
#include <vector>
|
||
using namespace std;
|
||
|
||
int n; // 节点数量
|
||
vector<int> father = vector<int> (101, 0); // 按照节点大小定义数组大小
|
||
|
||
// 并查集初始化
|
||
void init() {
|
||
for (int i = 1; i <= n; i++) father[i] = i;
|
||
}
|
||
// 并查集里寻根的过程
|
||
int find(int u) {
|
||
return u == father[u] ? u : father[u] = find(father[u]);
|
||
}
|
||
|
||
// 判断 u 和 v是否找到同一个根
|
||
bool isSame(int u, int v) {
|
||
u = find(u);
|
||
v = find(v);
|
||
return u == v;
|
||
}
|
||
|
||
// 将v->u 这条边加入并查集
|
||
void join(int u, int v) {
|
||
u = find(u); // 寻找u的根
|
||
v = find(v); // 寻找v的根
|
||
if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
|
||
father[v] = u;
|
||
}
|
||
|
||
int main() {
|
||
int m, s, t, source, destination;
|
||
cin >> n >> m;
|
||
init();
|
||
while (m--) {
|
||
cin >> s >> t;
|
||
join(s, t);
|
||
}
|
||
cin >> source >> destination;
|
||
if (isSame(source, destination)) cout << 1 << endl;
|
||
else cout << 0 << endl;
|
||
}
|
||
```
|
||
|
||
|
||
## 其他语言版本
|
||
|
||
### Java
|
||
|
||
```Java
|
||
|
||
import java.util.*;
|
||
|
||
public class Main{
|
||
public static void main(String[] args) {
|
||
int N, M;
|
||
Scanner scanner = new Scanner(System.in);
|
||
N = scanner.nextInt();
|
||
M = scanner.nextInt();
|
||
DisJoint disJoint = new DisJoint(N + 1);
|
||
for (int i = 0; i < M; ++i) {
|
||
disJoint.join(scanner.nextInt(), scanner.nextInt());
|
||
}
|
||
if(disJoint.isSame(scanner.nextInt(), scanner.nextInt())) {
|
||
System.out.println("1");
|
||
} else {
|
||
System.out.println("0");
|
||
}
|
||
}
|
||
|
||
}
|
||
|
||
//并查集模板
|
||
class DisJoint{
|
||
private int[] father;
|
||
|
||
public DisJoint(int N) {
|
||
father = new int[N];
|
||
for (int i = 0; i < N; ++i){
|
||
father[i] = i;
|
||
}
|
||
}
|
||
|
||
public int find(int n) {
|
||
return n == father[n] ? n : (father[n] = find(father[n]));
|
||
}
|
||
|
||
public void join (int n, int m) {
|
||
n = find(n);
|
||
m = find(m);
|
||
if (n == m) return;
|
||
father[m] = n;
|
||
}
|
||
|
||
public boolean isSame(int n, int m){
|
||
n = find(n);
|
||
m = find(m);
|
||
return n == m;
|
||
}
|
||
|
||
}
|
||
|
||
```
|
||
|
||
### Python
|
||
|
||
```python
|
||
|
||
class UnionFind:
|
||
def __init__(self, size):
|
||
self.parent = list(range(size + 1)) # 初始化并查集
|
||
|
||
def find(self, u):
|
||
if self.parent[u] != u:
|
||
self.parent[u] = self.find(self.parent[u]) # 路径压缩
|
||
return self.parent[u]
|
||
|
||
def union(self, u, v):
|
||
root_u = self.find(u)
|
||
root_v = self.find(v)
|
||
if root_u != root_v:
|
||
self.parent[root_v] = root_u
|
||
|
||
def is_same(self, u, v):
|
||
return self.find(u) == self.find(v)
|
||
|
||
|
||
def main():
|
||
import sys
|
||
input = sys.stdin.read
|
||
data = input().split()
|
||
|
||
index = 0
|
||
n = int(data[index])
|
||
index += 1
|
||
m = int(data[index])
|
||
index += 1
|
||
|
||
uf = UnionFind(n)
|
||
|
||
for _ in range(m):
|
||
s = int(data[index])
|
||
index += 1
|
||
t = int(data[index])
|
||
index += 1
|
||
uf.union(s, t)
|
||
|
||
source = int(data[index])
|
||
index += 1
|
||
destination = int(data[index])
|
||
|
||
if uf.is_same(source, destination):
|
||
print(1)
|
||
else:
|
||
print(0)
|
||
|
||
if __name__ == "__main__":
|
||
main()
|
||
|
||
|
||
```
|
||
|
||
|
||
### Go
|
||
|
||
```go
|
||
|
||
package main
|
||
|
||
import (
|
||
"fmt"
|
||
)
|
||
|
||
const MaxNodes = 101
|
||
|
||
var n int
|
||
var father [MaxNodes]int
|
||
|
||
// 初始化并查集
|
||
func initialize() {
|
||
for i := 1; i <= n; i++ {
|
||
father[i] = i
|
||
}
|
||
}
|
||
|
||
// 并查集里寻根的过程
|
||
func find(u int) int {
|
||
if u == father[u] {
|
||
return u
|
||
}
|
||
father[u] = find(father[u])
|
||
return father[u]
|
||
}
|
||
|
||
// 判断 u 和 v 是否找到同一个根
|
||
func isSame(u, v int) bool {
|
||
return find(u) == find(v)
|
||
}
|
||
|
||
// 将 v->u 这条边加入并查集
|
||
func join(u, v int) {
|
||
rootU := find(u)
|
||
rootV := find(v)
|
||
if rootU != rootV {
|
||
father[rootV] = rootU
|
||
}
|
||
}
|
||
|
||
func main() {
|
||
var m, s, t, source, destination int
|
||
fmt.Scan(&n, &m)
|
||
initialize()
|
||
for i := 0; i < m; i++ {
|
||
fmt.Scan(&s, &t)
|
||
join(s, t)
|
||
}
|
||
fmt.Scan(&source, &destination)
|
||
if isSame(source, destination) {
|
||
fmt.Println(1)
|
||
} else {
|
||
fmt.Println(0)
|
||
}
|
||
}
|
||
|
||
|
||
```
|
||
|
||
### Rust
|
||
|
||
### JavaScript
|
||
|
||
```java
|
||
const r1 = require('readline').createInterface({ input: process.stdin });
|
||
// 创建readline接口
|
||
let iter = r1[Symbol.asyncIterator]();
|
||
// 创建异步迭代器
|
||
const readline = async () => (await iter.next()).value;
|
||
|
||
|
||
let N, M // 节点数和边数
|
||
let source, destination // 起点 终点
|
||
let father = [] // 并查集
|
||
|
||
|
||
// 并查集初始化
|
||
const init = () => {
|
||
for (let i = 1; i <= N; i++) father[i] = i;
|
||
}
|
||
|
||
// 并查集里寻根的过程
|
||
const find = (u) => {
|
||
return u == father[u] ? u : father[u] = find(father[u])
|
||
}
|
||
|
||
// 将v->u 这条边加入并查集
|
||
const join = (u, v) => {
|
||
u = find(u)
|
||
v = find(v)
|
||
if (u == v) return // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
|
||
father[v] = u
|
||
}
|
||
|
||
// 判断 u 和 v是否找到同一个根
|
||
const isSame = (u, v) => {
|
||
u = find(u)
|
||
v = find(v)
|
||
return u == v
|
||
}
|
||
|
||
|
||
(async function () {
|
||
// 读取第一行输入
|
||
let line = await readline();
|
||
[N, M] = line.split(' ').map(Number);
|
||
|
||
// 初始化并查集
|
||
father = new Array(N)
|
||
init()
|
||
|
||
// 读取边信息, 加入并查集
|
||
for (let i = 0; i < M; i++) {
|
||
line = await readline()
|
||
line = line.split(' ').map(Number)
|
||
join(line[0], line[1])
|
||
}
|
||
|
||
// 读取起点和终点
|
||
line = await readline(); //JS注意这里的冒号
|
||
[source, destination] = line.split(' ').map(Number)
|
||
|
||
if (isSame(source, destination)) return console.log(1);
|
||
console.log(0);
|
||
})()
|
||
```
|
||
|
||
|
||
|
||
### TypeScript
|
||
|
||
### PhP
|
||
|
||
### Swift
|
||
|
||
### Scala
|
||
|
||
### C#
|
||
|
||
### Dart
|
||
|
||
### C
|
||
|