Блог пользователя TMB

Проблема с поиском в глубину. Пожалуйста помогите разобраться
Автор TMB, история, 9 лет назад, По-русски

Я написал два почти одинаковых кода. Но вторая программа проходит по всем вершинам графа, что не делает первая программа, пожалуйста объясните почему?

using namespace std;

int i,n,m,x,y,used[10001];

vector g[100001];

void dfs(int v){

used[v]=1;

//cout<<v<<endl;

for(i=0;i<g[v].size();i++){

    if (used[g[v][i]]!=1) dfs(g[v][i]);

}

}

int main(){

cin>>n>>m;

for(i=0;i<m;i++){

    cin>>x>>y;

    g[x].push_back(y);

    g[y].push_back(x);

}

dfs(1);

return 0;

}

using namespace std;

int i,n,m,x,y,used[10001];

vector g[100001];

void dfs(int v){

used[v]=1;

//cout<<v<<endl;

for (auto i : g[v]){

    if (used[i]!=1) dfs(i);

}

}

int main(){

cin>>n>>m;

for(i=0;i<m;i++){

    cin>>x>>y;

    g[x].push_back(y);

    g[y].push_back(x);

}

dfs(1);

return 0;

}

  • Проголосовать: нравится
  • -12
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

for(i=0;i<g[v].size();i++)
должен быть
for(int i=0;i<g[v].size();i++)
и думаю достаточно... но не уверен

→ Ответить
»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

Пожалуйста, не надо копировать код в пост. Используйте ссылки на посылки Codeforces, pastebin.com или ideone.com.

Это не паскаль, не объявляйте глобальные переменные-счётчики циклов. Если так делаете — огребаете, когда пробуете использовать одну и ту же переменную в разных функциях. Объявляйте переменные только там, где они в первый раз нужны (то есть даже не в начале процедуры). Например:

for (int i = 0; i < 10; i++) { // объявили переменную i, она видна только внутри цикла
}

// вот тут уже не видна
i = 10; // это не скомпилируется, переменной i вне цикла нет

int sum = 0; // переменная sum будет видна отсюда и до закрывающей фигурной скобки
for (int i = 0; i < 10; i++) { // новый цикл, новая переменная i
  // тут есть sum и новая переменная i
}
// а вот тут - уже только sum
→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Спасибо вам большое за хорошее объяснение, теперь мне все ясно

    → Ответить