How to prove/disprove this algorithm time complexity is O(M+N) amortized?

The following problem on leetcode has 2 described solution. Let N be the number of input equations and M be the number of queries:

• One uses union find and is O((M+N)log*(N))
• One uses DFS and is O(M*N)

However it seems to me that answering all queries at the end with DFS will have an O(M+N) runtime. The below code passed all tests and was accepted by the OJ.

General outline

• Build a graph. Each equation (a/b) = x creates two weighted edges from a to b with weight x, and from b to a with weight 1/x.
• I run DFS over all variables and record the connected components. For each letter, I maintain in which connected components it is via component_map.
• Each var in the component has a value V = captain/var, where captain was the first variable inserted
• Then for each query I can answer when both belongs to the same component without need of backtraking since (captain/var1* var2/captain = var2/var1)

The key differences between my DFS solution and theirs are:

• I do not need to backtrack due to last bullet above
• I answer all queries at once at the end

My reasoning is that every single operation I do is amortized O(1), basically with hash maps and vectors. I run DFS inside a loop with N iteration, but the sum complexity of all my DFS calls will be O(M+N) as every node is only visited once.

I hence believe this solution to be O(M+N).

Question: Am I correct? Can you prove the time complexity of this algorithm whatever it is?

class Solution {
public:
        typedef unordered_map<string,double> component;     // var --> captain/var
        typedef unordered_map<string,component> components; // captain --> component , each component identified by its captain.
        typedef unordered_map<string,string> component_map; // var --> captain, to what component this var belongs?
        typedef unordered_map<string, vector<pair<string,double>>> adjacency_list;
    
    void DFS(const string& node, component& compo, adjacency_list& adj, double value, unordered_set<string>& visited,component_map& m, const string& captain)
    {
        for(auto p: adj[node])
        {
            if(compo.find(p.first) == compo.end())
            {
                visited.insert(p.first);
                m.insert({p.first,captain}); // this letter belongs to this "captain component"
                compo.insert({p.first,value*p.second}); // insert L,V
                DFS(p.first,compo,adj,value*p.second,visited,m,captain);   
            }
        }   
    }
    
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries)
    {
        adjacency_list adj;
        for(int i=0;i<equations.size();++i)
        {
            string a = equations[i][0];
            string b = equations[i][1];
            double v = values[i];
            
            auto it = adj.find(a);
            if( it == adj.end())
            {
                adj.insert({a,{}});
                it = adj.find(a);
            }
            it->second.push_back({b,v});
            
            it = adj.find(b);
            if( it == adj.end())
            {
                adj.insert({b,{}});
                it = adj.find(b);
            }
            it->second.push_back({a,1/v});
        }
        
        components cps;
        unordered_set<string> visited;
        component_map m;
        
        for(int i=0;i<equations.size();++i)
        {
            string a = equations[i][0];
            if(visited.find(a)==visited.end())
            {
                auto it = cps.insert({a,{}}).first;
                DFS(a,it->second,adj,1,visited,m,a);
            }
            
            string b = equations[i][1];
            if(visited.find(b)==visited.end())
            {
                auto it = cps.insert({b,{}}).first;
                DFS(b,it->second,adj,1,visited,m,a);
            }
        }
        
        vector<double> res;
        for(auto& q:queries)
        {
            auto it0 = m.find(q[0]);
            auto it1 = m.find(q[1]);
            
            if(it0 != m.end() && it1 != m.end() && it0->second == it1->second)
            {
                auto& captain = it0->second;
                auto& cp = cps[captain];
                res.push_back(cp[q[1]]/cp[q[0]]);
            }
            else
            {
                res.push_back(-1.0);
            }
        }
        
        return res;
        
    }
};