Day-59-卡玛笔记
目录
Day 59 卡玛笔记
这是基于 的每日打卡
题目描述
给定一个包含 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。
并查集
class UnionFind:
def __init__(self,size): # 传入并查集大小
self.father=[0]*(size+1)
for i in range(1,size+1):
self.father[i]=i # 初始时元素自己指向自己
def find(self,elem):
if self.father[elem]!=elem:
self.father[elem]=self.find(self.father[elem])
# 将本层路径压缩的结果返回给上一层
return self.father[elem]
def union(self,u,v):
f1=self.find(u)
f2=self.find(v)
if f1==f2:
# 说明在同一个集合
return
else:
self.father[f2]=f1
def isSame(self,u,v):
return self.find(u)==self.find(v)
n,m=map(int,input().split())
uf=UnionFind(n+1) # 实例化并查集
for _ in range(m):
u,v=map(int,input().split())
uf.union(u,v)
s,e=map(int,input().split())
if uf.isSame(s,e):
print(1)
else:
print(0)运行结果
