-2

I was implemeting a graph theory question in Cpp using STL. While compiling the following code snippet in my local machine, I am not getting any compile time error, even with compiling using the following flags:

-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

But when I am submitting the code to the following question: https://practice.geeksforgeeks.org/problems/count-the-paths/0 I am getting segmentation fault. Below is the code snippet, if you find any error, please point out.

#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;
}
aji13
  • 75
  • 8
  • 3
    Don't use `#define` in C++, use `const`. – tadman Aug 03 '20 at 19:06
  • 3
    What is `#define int long long`? Don't do this either. Use `uint64_t` or whatever from [``](https://en.cppreference.com/w/cpp/types/integer). – tadman Aug 03 '20 at 19:07
  • You're not validating the inputs. Are the numbers being read into `a` and `b` 0-based or 1-based? – 1201ProgramAlarm Aug 03 '20 at 19:08
  • 4
    `#define int long long` -- Do not do this. This is one of the worst abuses of the preprocessor known to C++ programming. – PaulMcKenzie Aug 03 '20 at 19:12
  • Did you try running the same code but replacing subscript operators (`[...]`) with `vector::at()`? You probably went past the end of a vector when iterating or getting user inputs. You could also run your program in valgrind to catch any out-of-bounds memory access. – Jan Schultke Aug 03 '20 at 19:12
  • 1
    Also this: `#define endl "\n" ` -- Another abuse of the preprocessor. There is a big difference between `endl` and `\n`, just like there is a difference between `int` and `long long int`. And then `signed main() ` -- that should be `int main()`. What books and/or tutorial is having you write C++ in this manner? – PaulMcKenzie Aug 03 '20 at 19:14
  • 4
    Please don't use competition sites as a learning resource, because all they all they really teach are bads habits. Some of them are already mentioned, others include using global variables, one-letter variable names without meaning, misuse of preprocessor macros in general, using [bad header files](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h), [`using namespace std;`](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice), the first three lines of the `main` function, and a couple more. – Some programmer dude Aug 03 '20 at 19:16
  • Doesn't do anything for me. It just stops and waits for user input. – user4581301 Aug 03 '20 at 19:21
  • 1
    A classic clue to undefined behavior is when code works differently on different platforms. – Mark Ransom Aug 03 '20 at 19:24
  • 1
    *I am not getting any compile time error* -- If code compiles without error, all that means is that there are no syntax errors. It does not mean the program is logically correct. If all that was needed for a program to work is to compile with no errors, there would be no such thing as bugs. – PaulMcKenzie Aug 03 '20 at 19:40
  • 1
    Also including internal STL headers instead of the proper `vector` and `iostream` headers and working around missing definitions by using the preprocessor. Don't do that! – TainToTain Aug 03 '20 at 19:49
  • Redefining `int` has undefined behaviour. – molbdnilo Aug 03 '20 at 20:25
  • I understand the practices, I have followed in the code is wrong. I only used to do it to speed up my typing while being in contests. – aji13 Aug 12 '20 at 18:17

1 Answers1

0

Your code has several errors, I've removed them all and run the code. It compiled fine and work properly on provided input. But there are some problems with your implementation style and also with problem. To understand what is wrong with your code(actually, its not only your code's fault, the problem is also wrong), let me explain first why the problem is wrong:

Statement:
Given a directed graph, a source vertex ‘s’ and a destination vertex ‘d’, print the count of all paths from given ‘s’ to ‘d’.

Input:
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.

Output:
Single line output, print the count of all paths from 's' to 'd'.

It seems ok at first, but see, there's not talk about cycle. If there's any cycle, then, this problem could have infinite answer.

Now, examine the input:

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

The above (note this) lines shows two edges, those create a cycle. but, your code still works, why? cause, your code makes check[source] = true. But what if the cycle does not include source but other vertices...then, this code will lead to stackoverflow and sometimes stackoverflow raises SIGSEGV (segmentation violation) signal.

This problem can still be solved with some work around, but it'll be solving a wrong problem with wrong rules and wrong understanding(this happens sometime in problem solving and competitive programming). So, I didn't try that.

[P.S.]: competitive programming or sport programming is not bad at all. its actually quite effective to learn ds and algo. but choose better sites like topcoder, codeforces, codechef, hackerrank, leetcode, atcoder, uva, lightoj and the list goes on...but those i've noted are actually quite good.

reyad
  • 1,392
  • 2
  • 7
  • 12