Nvidia Intern 笔试回忆

Nvidia intern compute arch 的笔试回忆，感觉强度拉满，两个半小时6道编程题，难度堪比ACM，需要自己写好输入输出（ACM好歹有个签到题 = =），图论的题比较多，跟大厂面试题不是同一level....

前情提示🔔：

对于不确定行数字符串输入组的c++ 11输入模版为：

int main()

{

        string s;

        while(getline(cin,s))

        {

              cout<<s<<endl;

        }

}

1.graph

题目大意：给你一个无向图，图中必有一环， 返回每个顶点到环的距离（在环里的点到环的距离是0）

数据格式：

节点个数 边个数

所有边的一个顶点

所有边的另一个顶点

样例输入：

7 7

0 1 2 1 3 4 5

1 2 0 3 4 5 6

样例输出：

0 0 0 1 2 3 4

解题思路（来自chatgpt）：

要解决这个问题，我们可以使用图论中的 BFS（广度优先搜索）算法。具体步骤如下：

1. 检测环：首先，我们需要找到图中的一个环。
2. 标记环上的顶点：将环上的顶点的距离标记为 0。
3. 计算每个顶点到环的距离：从环上的顶点开始使用 BFS 来计算其他顶点到环的距离。

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>using namespace std;// DFS to find a cycle in the graph
bool findCycle(int u, int parent, vector<vector<int>>& graph, vector<int>& visited, vector<int>& parentTrack, vector<int>& cycle) {visited[u] = 1;for (int v : graph[u]) {if (v == parent) continue;if (visited[v] == 0) {parentTrack[v] = u;if (findCycle(v, u, graph, visited, parentTrack, cycle)) return true;} else if (visited[v] == 1) {// Found a cyclecycle.push_back(v);for (int x = u; x != v; x = parentTrack[x]) {cycle.push_back(x);}cycle.push_back(v);return true;}}visited[u] = 2;return false;
}vector<int> distancesToCycle(int n, vector<vector<int>>& edges) {vector<vector<int>> graph(n);for (const auto& edge : edges) {graph[edge[0]].push_back(edge[1]);graph[edge[1]].push_back(edge[0]);}vector<int> visited(n, 0), parentTrack(n, -1), cycle;for (int i = 0; i < n; ++i) {if (visited[i] == 0 && findCycle(i, -1, graph, visited, parentTrack, cycle)) {break;}}unordered_set<int> cycleNodes(cycle.begin(), cycle.end());vector<int> dist(n, -1);queue<int> q;// Mark all cycle nodes with distance 0for (int node : cycle) {dist[node] = 0;q.push(node);}// BFS to find shortest distance to cycle for all nodeswhile (!q.empty()) {int u = q.front();q.pop();for (int v : graph[u]) {if (dist[v] == -1) {  // Not visiteddist[v] = dist[u] + 1;q.push(v);}}}return dist;
}int main() {int n, m;cin >> n >> m;vector<vector<int>> edges(m, vector<int>(2));for (int i = 0; i < m; ++i) {cin >> edges[i][0];}for (int i = 0; i < m; ++i) {cin >> edges[i][1];}vector<int> result = distancesToCycle(n, edges);for (int i = 0; i < n; ++i) {cout << result[i] << " ";}cout << endl;return 0;
}

2.graph

给你一个无向图，图中必有一环，每个顶点可以视为一个管道，顶点的值是管道的高度，两个顶点联通表示两个管道互通，可以通水。返回在每个顶点高度水位下，通水的管道(包括自身)。

数据格式：

顶点个数 边个数

顶点值

每条边的两个顶点

样例输入：

6 6

2 3 5 1 6 4

0 1

1 2

2 0

0 3

1 4

2 5

样例输出：

[0,3]

[0,1,3]

[0,1,2,3,5]

[3] 

[0,1,2,3,4,5]

[0,1,2,3,5]

解题思路（来自chatgpt）：

要解决这个问题，我们需要执行以下步骤：

1. 构建图：用邻接表表示无向图。
2. 查找环：使用 DFS 找到图中的一个环。
3. 通水检测：对于每个顶点的高度，使用 BFS 从环的节点开始，找到所有在该高度下连通的节点。