当前位置：首页 > news >正文

寒假集训9——图论

news 2026/5/11 4:59:42

P3916 图的遍历

题目描述

给出 N 个点，M 条边的有向图，对于每个点 v，令 A(v) 表示从点 v 出发，能到达的编号最大的点。现在请求出 A(1),A(2),…,A(N) 的值。

输入格式

第 1 行 2 个整数 N,M，表示点数和边数。

接下来 M 行，每行 2 个整数 Ui,Vi，表示边 (Ui,Vi)。点用 1,2,…,N 编号。

输出格式

一行 N 个整数 A(1),A(2),…,A(N)。

输入输出样例

输入 #1复制

4 3 1 2 2 4 4 3

输出 #1复制

4 4 3 4

说明/提示

对于 60% 的数据，1≤N,M≤103。
对于 100% 的数据，1≤N,M≤105。

这样会超时，有一个测试点过不了。

其实刚刚开始提交第一版不带标记的代码时，我所有测试点都超时了。标记状态的st数组我是在和科技交流之后才想起来。
这是邻接表的写法，因为1e5的数据范围太大了，开1e5 的二维数组开不了，所以不能用邻接矩阵。但是链式前向星我理解的不是很好，所以就想起了这个邻接表的写法。
当时我第一次写的是vecrtor>，因为我接触到的好像都是链表头插。但是因为超时了，所以就觉得vector好像和list在这题大差不差，就想着用vector能不能优化一下。没想到还是没成功。

#include<iostream> #include<vector> using namespace std; const int N = 1e5 + 10; vector <vector<int>> g(N); void dfs(int cur,int&maxn, vector <bool>& st) { st[cur] = true; { for (auto e : g[cur]) { maxn = max(maxn, e); if(st[e]==false) dfs(e, maxn, st); } } } int main() { int n, m; cin >> n >> m; //m条边 for (int i = 1;i <= m;i++) { int u, v; cin >> u >> v; g[u].push_back(v); } //n个点 for (int i = 1;i <= n;i++) { int maxn = i; int cur = i; //标记访问过的点！！！ //st数组不能是全局，必须开局部！！！ //并且作为函数参数传递 vector <bool> st(N, false); dfs(cur, maxn, st); cout << maxn << " "; } return 0; }

我现在就想着输入边的时候就顺带更新答案数组，看看可不可行，这样不用建邻接表，也不用dfs。应该不至于超时。但现实证明不行，科技给的解释如下：

1.忽略了传递性（A→B→C 时，A应该能到C）
2.只更新了边的一端
3.没有利用历史信息

最后，借鉴了题解和学长的代码。

反向图+DFS的降维打击 | O(n+m)优雅解法

1.通过反向建图巧妙转化问题
2.利用从大到小的顺序保证正确性
3.使用DFS传播标记高效计算
4.简单的剪枝避免重复计算

AC代码（详细注释版）

#include<iostream> #include<vector> using namespace std; const int N = 1e5 + 10; vector <int> g[N];//存图 int ans[N];//存答案 //正在访问的点，当前传播的值 void dfs(int cur, int val) { //如果当前顶点已经标记过，直接返回 if (ans[cur] != 0) return; //顶点 cur能到达的最大编号是 val ans[cur] = val; for (auto e : g[cur]) dfs(e, val); } int main() { int n, m; cin >> n >> m; //【m条边】 for (int i = 1;i <= m;i++) { int u, v; cin >> u >> v; //建反图！！！ g[v].push_back(u); } //【n个点】 for (int i = n;i >= 1;i--) dfs(i, i); //i号点能到达的最大编号至少是自己（i） for (int i = 1;i <= n;i++) cout << ans[i] << " "; return 0; }

AC代码（纯享版）

#include<iostream> #include<vector> using namespace std; const int N = 1e5 + 10; vector <int> g[N]; int ans[N]; void dfs(int cur, int val) { if (ans[cur] != 0) return; ans[cur] = val; for (auto e : g[cur]) dfs(e, val); } int main() { int n, m; cin >> n >> m; for (int i = 1;i <= m;i++) { int u, v; cin >> u >> v; g[v].push_back(u); } for (int i = n;i >=1;i--) dfs(i, i); for (int i = 1;i <= n;i++) cout << ans[i] << " "; return 0; }

B3643 图的存储

题目描述

给定一个 n 个顶点 m 条边的无向图。请以邻接矩阵和邻接表的形式输出这一张图。

输入格式

第一行输入两个正整数 n 和 m，表示图的顶点数和边数。

第二行开始，往后 m 行，每行输入两个以空格隔开的正整数 u,v，表示 u,v 顶点之间有一条边直接相连。

输出格式

首先输出 n 行 n 列的矩阵，以空格隔开每一行之间的数表示邻接矩阵。第 i 行第 j 列的数为 1 则表示顶点 i,j 之间有一条边直接相连；若为 0 则表示没有直接相连的边。

再往后输出 n 行。第 i 行首先先输出一个整数 di，表示这个顶点的度数，再按照从小到大的顺序，依次输出与顶点 i 直接相连的所有顶点。

输入输出样例

输入 #1复制

5 5 1 2 2 3 3 5 1 3 3 4

输出 #1复制

0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 0 0 0 1 0 0 2 2 3 2 1 3 4 1 2 4 5 1 3 1 3

说明/提示

样例的图如图所示：

数据保证，对于所有数据，1≤n≤1000，1≤m≤105，且图无重边无自环。

记得排序再输出就行。

#include<iostream> #include<vector> #include<algorithm> using namespace std; const int N = 1e3 + 10; vector <int> glist[N];//邻接表 int gmat[N][N];//邻接矩阵 int degree[N];//度数 int main() { int n, m; cin >> n >> m; for (int i = 1;i <= m;i++) { int u, v; cin >> u >> v; glist[u].push_back(v); glist[v].push_back(u); gmat[u][v] = 1; gmat[v][u] = 1; degree[u]++; degree[v]++; } for (int i = 1;i <= n;i++) { for (int j = 1;j <= n;j++) cout << gmat[i][j] << " "; cout << endl; } for (int i = 1;i <= n;i++) { cout << degree[i] << " "; sort(glist[i].begin(), glist[i].end()); for (int e : glist[i]) cout << e << " "; cout << endl; } return 0; }