2026年9月GESP真题及题解C七级必经之路题目描述给定一张有n nn个结点m mm条边的有向图G GGG GG中的结点依次以1 , 2 , … , n 1,2,\ldots,n1,2,…,n编号。第i ii条边1 ≤ i ≤ m 1\le i\le m1≤i≤m从结点u i u_iui​指向结点v i v_ivi​。G GG中任一入度为0 00的结点可以作为合法起点任一出度为0 00的结点可以作为合法终点。如果G GG中所有可能的从合法起点到合法终点的路径都会经过结点u uu则称u uu是必经点。注意必经点可以为合法起点或合法终点。请你求出G GG中所有必经点的编号。例如在下图中合法起点有点1 11与点2 22合法终点有点7 77与点8 88。(1) (5)----(7) \ ^ \ ^ v / v / (3) / (6) ^ \ / \ / v / v (2)----(4) (8)所有合法起点到合法终点的路径为1 → 3 → 4 → 5 → 7 1\to 3\to 4\to 5\to 71→3→4→5→71 → 3 → 4 → 5 → 6 → 7 1\to 3\to 4\to 5\to 6\to 71→3→4→5→6→71 → 3 → 4 → 5 → 6 → 8 1\to 3\to 4\to 5\to 6\to 81→3→4→5→6→82 → 3 → 4 → 5 → 7 2\to 3\to 4\to 5\to 72→3→4→5→72 → 3 → 4 → 5 → 6 → 7 2\to 3\to 4\to 5\to 6\to 72→3→4→5→6→72 → 3 → 4 → 5 → 6 → 8 2\to 3\to 4\to 5\to 6\to 82→3→4→5→6→82 → 4 → 5 → 7 2\to 4\to 5\to 72→4→5→72 → 4 → 5 → 6 → 7 2\to 4\to 5\to 6\to 72→4→5→6→72 → 4 → 5 → 6 → 8 2\to 4\to 5\to 6\to 82→4→5→6→8因此必经点有两个编号分别为4 , 5 4,54,5。输入格式第一行两个正整数n , m n,mn,m表示有向图G GG中的结点数与边数。接下来m mm行每行两个正整数u i , v i u_i,v_iui​,vi​表示一条从结点u i u_iui​指向结点v i v_ivi​的有向边。保证G GG中至少有一个合法起点至少有一个合法终点且至少存在一条从一个合法起点到一个合法终点路径同时不存在孤立点即出度和入度都为0 00的点。输出格式第一行一个整数表示必经点的数量k kk。如果存在必经点则第二行从小到大输出G GG中所有必经点的编号。输入输出样例 1输入 18 9 1 3 2 3 3 4 4 5 5 6 6 7 6 8 2 4 5 7输出 12 4 5输入输出样例 2输入 28 9 1 3 2 3 3 4 4 5 5 6 6 7 6 8 2 5 4 7输出 20说明/提示对于40 % 40\%40%的测试点保证1 ≤ n ≤ 100 1\le n\le 1001≤n≤1001 ≤ m ≤ 200 1\le m\le 2001≤m≤200。对于所有测试点保证1 ≤ n ≤ 1000 1\le n\le 10001≤n≤10001 ≤ m ≤ 2000 1\le m\le 20001≤m≤2000。保证G GG中至少有一个合法起点至少有一个合法终点且至少存在一条从一个合法起点到一个合法终点路径同时不存在孤立点即出度和入度都为0 00的点。思路分析本题要求找出所有从任意合法起点到任意合法终点的路径都必须经过的结点。合法起点入度为 (0) 的结点。合法终点出度为 (0) 的结点。判断结点 (u) 是否为必经点可以转化为如果删除结点 (u) 后仍然存在某条从合法起点到合法终点的路径那么这条路径在原图中不经过 (u)所以 (u) 不是必经点。如果删除结点 (u) 后不存在任何从合法起点到合法终点的路径那么原图中所有合法路径都必然经过 (u)所以 (u) 是必经点。因此可以枚举每个结点 (u)在删除 (u) 的图上从所有合法起点排除 u出发做 BFS看能否到达任意合法终点排除 u。若不能到达则 (u) 是必经点。数据范围n ≤ 1000 n \le 1000n≤1000m ≤ 2000 m \le 2000m≤2000每次 BFS 复杂度 O(nm)总复杂度 O(n(nm))。代码实现#includebits/stdc.husingnamespacestd;intn,m;//结点数和边数vectorintg[1005];//邻接表intd1[1005],d2[1005];//d1入度,d2出度boolf(intx){//检查删除x后是否还有合法路径vectorintq(n1);//BFS队列vectorcharv(n1,0);//访问标记inth0,t0;//队头h,队尾tfor(inti1;in;i){//枚举所有原合法起点if(d1[i]0i!x){//入度为0且不是删除点v[i]1;//标记起点q[t]i;//起点入队if(d2[i]0i!x)return1;//起点也是合法终点}}while(ht){//BFSintaq[h];//取出队头if(d2[a]0a!x)return1;//到达原合法终点for(inti0;i(int)g[a].size();i){//遍历出边intbg[a][i];//出边终点if(bx||v[b])continue;//跳过删除点和已访问点v[b]1;//标记访问q[t]b;//入队if(d2[b]0b!x)return1;//到达原合法终点}}return0;//不存在不经过x的路径}intmain(){cinnm;for(inti0;im;i){//读入m条边intu,v;//边起点和终点cinuv;//读入边g[u].push_back(v);//加入邻接表d2[u];//u出度加1d1[v];//v入度加1}vectorintr;//存储必经点for(inti1;in;i){//枚举每个结点if(!f(i))r.push_back(i);//删除后无路径则i必经}coutr.size()\n;//输出必经点数量if(!r.empty()){//存在必经点for(inti0;i(int)r.size();i){//输出编号if(i)cout ;//非第一个前加空格coutr[i];//输出编号}cout\n;//换行}return0;}功能分析读入有向图统计每个结点的入度和出度。合法起点为入度 (0) 的结点合法终点为出度 (0) 的结点。对每个结点 (u)删除 (u) 后从所有合法起点开始 BFS。BFS 过程中若到达任意合法终点说明存在一条不经过 (u) 的合法路径(u) 不是必经点。若 BFS 无法到达任何合法终点说明所有合法路径都经过 uu 是必经点。最后按编号从小到大输出所有必经点。各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}【秘籍汇总】完整csp信奥赛C学习资料1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转https://edu.csdn.net/course/detail/41081 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转4、csp信奥赛冲刺一等奖有效刷题题解信奥赛C普及组CSP-J一等奖通关刷题题单及题解https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转信奥赛C普及组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转5、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}