Re: [閒聊] 每日leetcode

作者: Rushia (みけねこ的鼻屎)   2025-01-27 18:47:03
https://leetcode.com/problems/course-schedule-iv
1462. Course Schedule IV
給你numCourses表示課程數量prerequisites[i] = [ai, bi]表示要修完ai的課才可以修
bi的課, queries[j] = [uj, vj]為判斷是否要先修uj才可以修vj,返回一個長度跟
queries一樣長的列表表示每次查詢的結果。
思路:
1.先依照先決條件建圖
2.使用dfs找出點i可以訪問到的所有點,標記connected[a][i],connected[b][i],...
= true
直接跑dfs會tle所以要加上記憶化搜索
3.直接判斷queries的查詢兩點是否有通就好
java code

Links booklink

Contact Us: admin [ a t ] ucptt.com