用c++数据结构来解决这个问题,不能使用stl容器,给出C++代码:给定n个点,m条边的有向图,对于每个点v,求f(v)表示从点v出发能到达的编号最大的点(包括自己在内)。 n,m≤105
时间: 2024-02-16 16:59:59 浏览: 95
好的,我可以提供一种解法。由于不能使用STL容器,我们可以使用数组和链表来实现。
具体思路是,对于每个点v,我们可以从它出发进行深度优先搜索,记录访问到的所有点,最后找出其中编号最大的点。为了避免重复访问,我们可以使用一个visited数组记录每个点是否已经被访问过。
代码如下:
```c++
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 100005
using namespace std;
int head[MAXN], nxt[MAXN], ver[MAXN], tot;
int n, m, f[MAXN], visited[MAXN];
void add(int x, int y) {
ver[++tot] = y;
nxt[tot] = head[x];
head[x] = tot;
}
void dfs(int u, int& maxId, int& visitedCnt) {
visited[u] = 1;
visitedCnt++;
if (u > maxId) maxId = u;
for (int i = head[u]; i; i = nxt[i]) {
int v = ver[i];
if (!visited[v]) dfs(v, maxId, visitedCnt);
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int x, y;
scanf("%d%d", &x, &y);
add(x, y);
}
for (int i = 1; i <= n; i++) {
int maxId = -1, visitedCnt = 0;
memset(visited, 0, sizeof(visited));
dfs(i, maxId, visitedCnt);
f[i] = maxId;
}
for (int i = 1; i <= n; i++) {
printf("%d ", f[i]);
}
return 0;
}
```
其中,head数组和nxt数组实现了链表,ver数组存储边的终点,tot表示边数。f数组记录每个点的答案。在dfs函数中,maxId记录访问到的最大编号,visitedCnt记录访问到的点数,用于判断是否存在从i出发无法到达的点。
阅读全文