I am trying to solve one competitive programming problem using c++ and DFS algorithm.
我正在尝试用C++和DFS算法来解决一个竞争性编程问题。
int main()
{
int n;
cin >> n;
vector <int> mygraph[n + 1]; // i need this to be global to use in dfs
bool visited[n + 1] = {};
...
//here I have to pass my vector mygraph, vertex where to start DFS and array of visited);
dfs(...);
}
void dfs(int vertex) {
// depth first search, recursive
// should use global mygraph and visited arrays or have them as parameters
}
My problem is that I cannot make "mygraph
" global, because it depands on size "n
". So I do not understand how to pass it to external function dfs
. If I just pass it as parameter it will be by value and not by refence, thus dfs that is recursive depth-first-search algorithm won't work.
我的问题是我不能使“mygraph”成为全局的,因为它依赖于大小“n”。所以我不知道如何将它传递给外部函数DFS。如果我只是将它作为参数传递,它将是按值传递的,而不是按引用传递的,因此递归深度优先搜索算法DFS将无法工作。
P.S. I am in 8th grade in school. I am studying by videos DFS
algorithm. I have studied some c++ syntax but I am still new to it and do not know some tricks yet. This is for competitive programming.
另外,我在学校读八年级。我正在学习视频DFS算法。我已经学习了一些C++语法,但我对它仍然是新手,还不知道一些诀窍。这是为竞技节目准备的。
I have tried to send mygraph
and visited as parameters to dfs
function, but I realised that those are passed by values not by reference.
I tried to mark mygraph
and visited as "by reference" using "&" symboo, but it turned out that it is prohibited in c++ to pass those "by reference".
I have tried to make them global
, but I cannot make them of my desired size n, because n comes from cin
.
我曾尝试将mygraph和vised作为参数发送给DFS函数,但我意识到这些参数是通过值传递的,而不是通过引用传递的。我试图使用“&”symboo标记mygraph并将其访问为“By Reference”,但事实证明,在c++中禁止传递那些“By Reference”。我试图使它们成为全局的,但我无法使它们达到我想要的大小n,因为n来自CIN。
更多回答
vector <int> mygraph[n + 1];
-- This is not legal C++. Arrays in C++ must have their size denoted by a compile-time constant, not a runtime variable. That should be std::vector<std::vector<int>> mygraph(n + 1);
. You make the same error here: bool visited[n + 1] = {};
-- That should be std::vector<bool> visited(n+1);
. The bottom line is to stop using competitive programming sites as learning tools for C++.
向量mygraph[n+1];--这不是合法的C++。C++中的数组的大小必须由编译时常量而不是运行时变量表示。这应该是std::VECTOR>mygraph(n+1);。您在这里也犯了同样的错误:Bool vised[n+1]={};--这应该是std::VECTORvised(n+1);。底线是停止使用竞争性编程站点作为C++的学习工具。
what you miss is not "tricks". Actually you should strive to avoid tricks and write plain simple code.
你错过的不是“花招”。实际上,您应该努力避免花招,编写简单明了的代码。
Did you want to declare a single vector that holds n + 1
elements, or n + 1
vectors? Your code, even though not legal, attempted to create n + 1
vectors. But this is just another sign that you can't learn C++ by doing competitive programming. Those competitive programming sites assume you know the computer language you will be using well-enough to never ask basic questions about how to use the language. If you don't know C++ but know some other computer language (python, Java, etc.), then use that language to answer the competitive coding site's questions.
您是想声明一个包含n+1个元素的向量,还是n+1个向量?您的代码虽然不合法,但仍试图创建n+1个向量。但这只是另一个迹象,表明你不能通过竞争编程来学习C++。那些竞争激烈的编程网站假设你对你将要使用的计算机语言了如指掌--足以让你永远不会问有关如何使用该语言的基本问题。如果您不懂C++,但知道一些其他计算机语言(Python、Java等),那么可以使用该语言来回答竞争对手的编码站点的问题。
std::vector<int> MyGraph;
in main: MyGraph.resize(n+1);
Std::向量MyGraph;Main中:MyGraph.resize(n+1);
@Jēkabs 1) Your code is not legal. 2) You should use std::vector
, as that is the class that is standard for dynamic arrays.
@JēKabs 1)您的代码不合法。2)您应该使用std::VECTOR,因为它是动态数组的标准类。
There's constraints in each competitive programming questions. Example:
在每一个竞争性编程问题中都有限制。示例:
Each test contains multiple test cases. The first line contains the
number of test cases t (1≤t≤100). The description of the test cases
follows.
The first line of each test case contains a single integer n
(1≤n≤100).
The second line of each test case contains n integers a[1],a[2],…,a[n]
(1≤a[i]≤10^9).
you can declare your mygraph globally based on the maximum of N in cosntraints.
您可以根据Cosntraint中N的最大值在全局范围内声明您的mygraph。
#include <iostream>
#include <vector>
using namespace std;
const int MAX_N = 105; // change it to the maximum of statement constraints + 1
vector<int>mygraph[MAX_N];
bool visited[MAX_N];
void dfs(int vertex);
int main()
{
int n;
cin >> n;
dfs(1);
}
void dfs(int vertex)
{
cout<<vertex<<'\n'; // implement yourself
}
更多回答
我是一名优秀的程序员,十分优秀!