重点就是:(点的访问次数)和(到达目的地路径条数)相等的点就是关键点。(也就是说每次到达终点都会访问的点就是关键点)
参考代码:
#include<bits/stdc++.h> using namespace std; int n, m,u,v,t=0,k=-1;//t记录到达终点路径条数,k表示关键点 vector<int> g[1000]; int vis[1000],vts[1000];//vis判断是否访问,vts记录所有路径到达终点时每个点的访问次数 void dfs(int x) { if (x == v) //到达终点 { for (int i =1; i <= n; i++)//记录频率 { vts[i] += vis[i]; } t++; //记录到达次数 return; } vis[x] = 1; for (int i = 0; i < g[x].size(); i++)//访问邻接表 { if (vis[g[x][i]] == 0) dfs(g[x][i]); } vis[x]=0; } int main() { cin >> n >> m; for (int i = 1; i <= m; i++) { cin >> u >> v; g[u].push_back(v);//无向图双向赋值 g[v].push_back(u); } cin >> u >> v; dfs(u); for (int i = 1; i <=n; i++) { if (vts[i] == t&&t!=0) k++; } cout << k; }
0.0分
11 人评分
简洁的代码浏览:1409 |
C语言程序设计教程(第三版)课后习题7.2 (C语言代码)浏览:529 |
输出九九乘法表 (C语言代码)浏览:555 |
川哥的吩咐 (C++代码)浏览:1016 |
C二级辅导-统计字符 (C语言代码)浏览:506 |
数列排序 (C语言代码)浏览:836 |
A+B for Input-Output Practice (IV) (C语言代码)浏览:457 |
WU-蓝桥杯算法提高VIP-交换Easy (C++代码)浏览:1119 |
C语言程序设计教程(第三版)课后习题7.2 (C语言代码)浏览:542 |
C语言程序设计教程(第三版)课后习题10.4 (C语言代码)浏览:886 |
买耨 2022-03-19 19:57:53 |
懂了vector<int> g[1000];是二维数组