current position:Home>leetcode 1971. Find if Path Exists in Graph(python)
leetcode 1971. Find if Path Exists in Graph(python)
2022-01-31 09:33:17 【Wang Daya】
「 This is my participation 11 The fourth of the yuegengwen challenge 11 God , Check out the activity details :2021 One last more challenge 」
describe
There is a bi-directional graph with n vertices, where each vertex is labeled from 0 to n - 1 (inclusive). The edges in the graph are represented as a 2D integer array edges, where each edges[i] = [ui, vi] denotes a bi-directional edge between vertex ui and vertex vi. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself.
You want to determine if there is a valid path that exists from vertex start to vertex end.
Given edges and the integers n, start, and end, return true if there is a valid path from start to end, or false otherwise.
Example 1:
Input: n = 3, edges = [[0,1],[1,2],[2,0]], start = 0, end = 2
Output: true
Explanation: There are two paths from vertex 0 to vertex 2:
- 0 → 1 → 2
- 0 → 2
Copy code
Example 2:
Input: n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], start = 0, end = 5
Output: false
Explanation: There is no path from vertex 0 to vertex 5.
Copy code
Note:
- 1 <= n <= 2 * 10^5
- 0 <= edges.length <= 2 * 10^5
- edges[i].length == 2
- 0 <= ui, vi <= n - 1
- ui != vi
- 0 <= start, end <= n - 1
- There are no duplicate edges.
- There are no self edges.
analysis
According to the meaning , Give an example with n A two-way graph of vertices , Each vertex is marked as 0 To n-1 A number in . The edges in the figure are represented as two-dimensional integer array edges , Each of them edges[i] = [ui, vi] It means a vertex ui And vertex vi Two way edges between . Each vertex pair is connected by at most one edge , And there are no edges with vertices connected to itself . The question asks to determine whether there is from the vertex start To the top end The effective path . Give edges and integers n、start and end , If there is a valid path from start to end , Then return to true, Otherwise return to false.
Use it directly BFS Ideas :
- If start be equal to end Go straight back to True ( I didn't expect this border situation , It led to a wrong submission !!)
- Will all edges There is a two-dimensional list of vertices in graph ,graph The length is n
- Initializes a length of n It's all about False Of visited list , Indicates whether a vertex has been accessed , If visited, it becomes True
- Initialize a queue stack , Store that has not been accessed and may be end The summit of , Add a vertex start
- When stack When it's not empty while loop , Take out stack The first element of is key , take visited[key] Set as True Indicates that you have been visited , If end stay graph[key] There has been a direct return in True , Otherwise it would be graph[key] Elements in that have not been accessed are added to stack in , Continue to cycle
- No legal path found at the end of the loop , Go straight back to False
answer
class Solution(object):
def validPath(self, n, edges, start, end):
"""
:type n: int
:type edges: List[List[int]]
:type start: int
:type end: int
:rtype: bool
"""
if start == end: return True
graph = [[] for i in range(n)]
for s,e in edges:
graph[s].append(e)
graph[e].append(s)
visited = [False for _ in range(n)]
stack = [start]
while stack:
key = stack.pop(0)
visited[key] = True
if end in graph[key]:
return True
for vertex in graph[key]:
if not visited[vertex]:
stack.append(vertex)
return False
Copy code
Running results
Runtime: 1612 ms, faster than 97.22% of Python online submissions for Find if Path Exists in Graph.
Memory Usage: 110.9 MB, less than 89.03% of Python online submissions for Find if Path Exists in Graph.
Copy code
Original link :leetcode.com/problems/fi…
Your support is my greatest motivation
copyright notice
author[Wang Daya],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/01/202201310933163862.html
The sidebar is recommended
- Django ORM details - fields, attributes, operations
- Python web crawler - crawling cloud music review (3)
- Stroke list in python (bottom)
- What cat is the most popular? Python crawls the whole network of cat pictures. Which one is your favorite
- [algorithm learning] LCP 06 Take coins (Java / C / C + + / Python / go / trust)
- Python shows the progress of downloading files from requests
- Solve the problem that Django celery beat prompts that the database is incorrectly configured and does not support multiple databases
- Bamboolib: this will be one of the most useful Python libraries you've ever seen
- Python quantitative data warehouse construction 3: data drop library code encapsulation
- The source code and implementation of Django CSRF Middleware
guess what you like
-
Python hashlib module
-
The cover of Python 3 web crawler development (Second Edition) has been determined!
-
The introduction method of executing Python source code or Python source code file (novice, please enter the old bird and turn left)
-
[Python basics] explain Python basic functions in detail, including teaching and learning
-
Python web crawler - crawling cloud music review (4)
-
The first step of scientific research: create Python virtual environment on Linux server
-
Writing nmap scanning tool in Python -- multithreaded version
-
leetcode 2057. Smallest Index With Equal Value(python)
-
Bamboolib: this will be one of the most useful Python libraries you've ever seen
-
Python crawler actual combat, requests module, python realizes capturing a video barrage
Random recommended
- [algorithm learning] 1108 IP address invalidation (Java / C / C + + / Python / go / trust)
- Test platform series (71) Python timed task scheme
- Java AES / ECB / pkcs5padding encryption conversion Python 3
- Loguru: the ultimate Python log solution
- Blurring and anonymizing faces using OpenCV and python
- How fast Python sync and async execute
- Python interface automation test framework (basic) -- common data types list & set ()
- Python crawler actual combat, requests module, python realizes capturing video barrage comments of station B
- Python: several implementation methods of multi process
- Sword finger offer II 054 Sum of all values greater than or equal to nodes | 538 | 1038 (Java / C / C + + / Python / go / trust)
- How IOS developers learn python programming 3-operator 2
- How IOS developers learn python programming 2-operator 1
- [Python applet] 8 lines of code to realize file de duplication
- Python uses the pynvml tool to obtain the working status of GPU
- Data mining: Python actual combat multi factor analysis
- Manually compile opencv on MacOS and Linux and add it to Python / C + + / Java as a dependency
- Use Python VTK to batch read 2D slices and display 3D models
- Complete image cutting using Python version VTK
- Python interface automation test framework (basic) -- common data types Dict
- Django (make an epidemic data report)
- Python specific text extraction in actual combat challenges the first step of efficient office
- Daily python, Part 8 - if statement
- Django model class 1
- The same Python code draws many different cherry trees. Which one do you like?
- Python code reading (Chapter 54): Fibonacci sequence
- Django model class 2
- Python crawler Basics
- Mapping 3D model surface distances using Python VTK
- How to implement encrypted message signature and verification in Python -- HMAC
- leetcode 1945. Sum of Digits of String After Convert(python)
- leetcode 2062. Count Vowel Substrings of a String(python)
- Analysis of Matplotlib module of Python visualization
- Django permission management
- Python integrated programming -- visual hot search list and new epidemic situation map
- [Python data collection] scripy realizes picture download
- Python interface automation test framework (basic part) -- loop statement of process control for & while
- Daily python, Chapter 9, while loop
- Van * Python | save the crawled data with docx and PDF
- Five life saving Python tips
- Django frequency control