【完整题单06、图论算法(拓扑排序)】【无】

目录知识框架No.0 筑基No.1 拓扑排序题目来源LeetCode-207. 课程表题目来源Acwing-164. 可达性统计知识框架No.0 筑基请先学习下知识点道友题目知识点大部分来源于此题目例题大部分来源于此No.1 拓扑排序题目来源LeetCode-207. 课程表题目描述题目思路核心考点拓扑排序解决「有向无环图 (DAG)」的环路检测判断是否能完成所有课程无环。模板化思路Kahn 算法 / BFS 版构建「邻接表」存储课程的依赖关系和「入度数组」每个课程的前置课程数初始化队列将入度为 0 的课程无前置课程入队BFS 遍历每次取出一个课程减少其后续课程的入度若后续课程入度变为 0 则入队统计已完成的课程数若等于总课程数说明无环返回 true否则返回 false。题目代码classSolution{public:boolcanFinish(intnumCourses,vectorvectorintprerequisites){// 1. 构建邻接表入度数组vectorvectorintadj(numCourses);// adj[i]课程i的后续课程vectorintinDegree(numCourses,0);// 入度前置课程数for(autop:prerequisites){intcurp[0],prep[1];adj[pre].push_back(cur);// 先修pre再修curinDegree[cur];}// 2. 初始化队列入度为0的课程queueintq;for(inti0;inumCourses;i){if(inDegree[i]0)q.push(i);}// 3. 拓扑排序intcount0;// 已完成的课程数while(!q.empty()){intuq.front();q.pop();count;// 遍历u的后续课程减少入度for(intv:adj[u]){inDegree[v]--;if(inDegree[v]0)q.push(v);}}// 4. 判断是否无环所有课程都完成returncountnumCourses;}};题目来源Acwing-164. 可达性统计题目描述题目思路下面这个是超时的dfs超时的应该用拓扑排序的题目代码#includebits/stdc.husingnamespacestd;#defineN100010#defineinf0x3f3f3f3f#definedebug(x)cout#x xendl;#defineLLlonglongconstintmod1e97;intn,m,k,d,g;intx,y,z;string str;charch;vectorintv[N];LL dp[N]{0};intvis[N];voiddfs(intindex,intnum){if(dp[index]!0){numnumdp[index];return;}vis[index]1;num;for(inti0;iv[index].size();i){if(vis[v[index][i]]0){dfs(v[index][i],num);}}}intmain(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cinnm;for(inti1;im;i){cinxy;v[x].push_back(y);}for(inti1;in;i){memset(vis,0,sizeof(vis));intnum0;dfs(i,num);dp[i]num;coutnumendl;}return0;}