Segmentation fault

#1

My code gives segmentation fault. Please help me to find the mistake.

#2

Your indexing was 0 based but u were using 1 based indexing.
I made some little changes please check.

#include<iostream>
#include<list>
using namespace std;


class Graph{
    int V;
    list<pair<int,int>>* l;
public:
    Graph(int v){
        V=v;
        l=new list<pair<int,int>>[V+1];
    }
    void addEdge(int u, int v, int z){
        l[u].push_back(make_pair(v,z));
        l[v].push_back(make_pair(u,z));
    }
    //will return count of subgraphs returning to parent node
    //we will update the ans by reference
    int dfsHelper(int src, bool*visited,int *count, int &ans){
        //mark the node visited
        visited[src]=true;
        count[src]=1;
        for(auto nbr_pair:l[src]){
            int nbr = nbr_pair.first;
            int wt = nbr_pair.second;
            if(!visited[nbr]){
                count[src]+=dfsHelper(nbr,visited,count,ans);
                //increment the node's contribution
                int nx = count[nbr];
                int ny = V-nx;
                ans+=2*min(nx,ny)*wt;
            }
        }
        //just before leaving the src parent
        return count[src];
    }

    int dfs(){
        bool *visited = new bool[V+1];
        int *count = new int[V+1];
        for(int i=0; i<=V; i++){
            visited[i]=false;
            count[i]=0;
        }
        int ans = 0;
        dfsHelper(1,visited,count,ans);
        return ans;
    }
};

int main(){
    // int t;
    // cin>>t;
    // while(t--){
    //     int v;
    //     cin>>v;
    //     Graph g(v);
    //     for(int i=0; i<v; i++){
    //         int u,y,z;
    //         cin>>u>>y>>z
    //         g.addEdge(u,y,z);
    //         cout<<g.dfs<<endl;
    //     }
    // }
    Graph g(4);
    g.addEdge(1,2,3);
    g.addEdge(2,3,2);
    g.addEdge(4,3,2);
    cout<<g.dfs();
}
#3
#4

solution not accepted on spoj

#5

Then I think your implementation might be wrong. I just corrected the part where it was showing segmentation fault

#6


Your nodes are starting from 1, so declare size of graph as 1 more than the number of nodes. I have made the correction in line 11. Please check it.

#7

@Madeshi-Chinmay-2159857244260221 I did it exactly how it is done in the video.

#8

@S19APP-PP0108 the output is zero. It should be 18 instead

#9

You must have copied something wrong. Please check it.
Meanwhile, please send the link of the question on hackerblocks.

#10

I’m not sure if the problem is in hackerblocks. The name of the video is holiday accomodation 2. It is in spoj. This is the link.

#11

Hard refresh your browser and try submitting it again. Also please recheck your code once again from the video.

#12

It is showing wrong answer in spoj

#13

Got correct answer for sample test cases?

#14

Yep. They passed when solving in my text editor.

#15

Try using long long int for all the variables.

#16

Still, wrong ans! https://ide.codingblocks.com/s/326698

#17

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.