I have read past discussions and even then I'm unable to pass it

#1

I know it is eulerian path question. Can you brief me about the logic??
(Please dont write this :
Count the number of vertices(count of the open ends) with odd degree in a component. If there is no vertex with odd degree, in a connected component, consider that there are two open ends, so add two to the count.

You can leave at most two open ends unpaired. That means, the number of pairings that need to be done are the minimum number of edges to be added.)

My code for reference:

It would be much better if you can give me a faulty test case as well!!!

Thank you!!

#2

@Aarnav-Jindal-1059677350830863 Please have a look!!

#3

Hey @ayushjain.iitg
I appreciate your belief in my doubt resolving skills. Thanks alot.
But this question has been assigned to the course mentor since it is kind of tricky. Rest assured you’ll get best assistance always. Best of luck !!

1 Like
#4

@ayushjain.iitg
You have already posted the explanation in your own doubt itself. So no point in repeating that. That is literally the entire gist of it. Take a look at this code snippet.


//Returns odd degree count
    ll dfsHelper(pii node, map &visited, map &degree)
    {
        visited[node] = true;

        ll ans = 0;
        if (degree[node] & 1)
        {
            ans++;
        }

        for (auto it : adjList[node])
        {
            if (!visited[it])
            {
                ans += dfsHelper(it, visited, degree);
            }
        }

        return ans;
    }

    ll dfs()
    {
        int component = 0;
        map visited;
        map degree;

        for (auto it : adjList)
        {
            for (auto child : adjList[it.first])
            {
                degree[child]++;
            }
        }

        ll totalOddDegreeCount = 0;

        for (auto it : adjList)
        {
            auto node = it.first;
            if (!visited[node])
            {
                ll oddDegreeCount = dfsHelper(node, visited, degree);
                if (oddDegreeCount == 0)
                    oddDegreeCount = 2;

                totalOddDegreeCount += oddDegreeCount;
                component++;
            }
        }

        return (totalOddDegreeCount - 2) / 2;
    }
#5

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.