Ошибка сегментации при отправке фрагмента кода в онлайн-компилятор, даже если он работает на локальном компьютере - PullRequest
Новая
       71

Ошибка сегментации при отправке фрагмента кода в онлайн-компилятор, даже если он работает на локальном компьютере

0 голосов
/ 03 августа 2020

Я реализовал вопрос теории графов в Cpp, используя STL. При компиляции следующего фрагмента кода на моем локальном компьютере я не получаю никаких ошибок времени компиляции, даже при компиляции с использованием следующих флагов: 

-Wall -Wextra -pedantic -std=c++11 -O2 -Wshadow -Wformat=2 -Wfloat-equal -Wconversion -Wlogical-op -Wshift-overflow=2 -Wduplicated-cond -Wcast-qual -Wcast-align -D_GLIBCXX_DEBUG -D_GLIBCXX_DEBUG_PEDANTIC -D_FORTIFY_SOURCE=2 -fsanitize=address -fsanitize=undefined -fno-sanitize-recover -fstack-protector

Но когда я отправляю код на следующий вопрос: https://practice.geeksforgeeks.org/problems/count-the-paths/0 Я получаю ошибку сегментации. Ниже приведен фрагмент кода. Если вы обнаружите ошибку, укажите ее. 

#include <bits/stdc++.h>
#define int long long
#define endl "\n" 
#define MAX 10e4
using namespace std;
vector<vector<int>> v(MAX);
vector<bool> check(MAX);
int path;

void dfs(int s, int d) {
    for (int i: v[s]) {
        if (i == d) {
            path++;
            continue;
        }
        if (!check[i]) {
            dfs(i, d);
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int t;
    cin >> t;
    while (t--) {
        int n, e;
        cin >> n >> e;
        int a, b;
        for (int i=0; i<e; i++) {
            cin >> a >> b;
            v[a].push_back(b);
        }
        int source, destination;
        cin >> source >> destination;
        check[source] = true; 
        dfs(source, destination);
        cout << path << endl;
    }
    
    return 0;
}

1 Ответ

0 голосов
/ 03 августа 2020

В вашем коде несколько ошибок, я удалил их все и запустил код. Он отлично скомпилирован и правильно работает с предоставленными данными. Но есть некоторые проблемы как с вашим стилем реализации, так и с проблемой. Чтобы понять, что не так с вашим кодом (на самом деле, это не только ошибка вашего кода, проблема также неправильна), позвольте мне сначала объяснить, почему проблема неправильная:

Заявление : Given a directed graph, a source vertex ‘s’ and a destination vertex ‘d’, print the count of all paths from given ‘s’ to ‘d’.

Ввод : First line consists of T test cases. First line of every test case consists of V and E, denoting the vertices and edges. Second line of every test case consists of 2*E spaced integers denoting the edge between vertices. Third line of every test case consists of S and D.

Выход : Single line output, print the count of all paths from 's' to 'd'.

Сначала вроде нормально, но, видите ли, о цикле речи не идет. Если есть какой-либо цикл, тогда у этой проблемы может быть бесконечный ответ.

Теперь проверьте ввод: 

1
4 6
0 1
0 2 // note this
0 3
2 0 // note this
2 1
1 3
2 3

В приведенных выше (обратите внимание на это) строках показаны два ребра, которые создают цикл . но ваш код все еще работает, почему? Потому что ваш код составляет check[source] = true. Но что, если цикл не включает source, но другие вершины ... тогда этот код приведет к переполнению стека, а иногда переполнение стека вызывает сигнал SIGSEGV (нарушение сегментации).

Эту проблему все же можно решить с помощью некоторых работать, но это будет решение неправильной проблемы с неправильными правилами и неправильным пониманием (это иногда случается при решении проблем и соревновательном программировании). Так что я этого не пробовал.

[PS]: соревновательное программирование или спортивное программирование - это совсем не плохо. на самом деле довольно эффективно изучать DS и AL go. но выбирайте лучшие сайты, такие как topcoder, codeforces, codechef, hackerrank, leetcode, atcoder, uva, lightoj, и список продолжается ... но те, что я отметил, на самом деле довольно хороши.

...