Find original array from array with pairs of adjacent elements Given an array composed of pairs, like this:
[[3,5],[1,5],[3,2],[1,4]]
Each element in the array (call it pair) means that pair[0] and pair[1] are adjacent in the original array. Note, they can come in either order. For instance, for the sample array above, the original array would be:
4,1,5,3,2 (or the reversed version of this)
How can I do this quickly? I tried doing this as follows, which works, but it's too slow:
Create a hashmap that maps adjacent elements. Map = {3: [5,2], 1: [5,4], 5: [1,3], 4: [1], 2:[3]}. My algorithm would then start with one of the keys that only has a corresponding value length of 1 (in this case either 4 or 2), and then add to an output array, and go through the hashmap. I.e. First I would add 4 to my output, and then go from key of 4 (with a corresponding value of 1), to the key of 1, with corresponding values of 5 and 4. I'd ignore 4 (since it's already in output), and add 5, then go to the key of 5, and so on and so forth. This is too slow! Is there a better algorithm?
Use indegree or DFS:
    unordered_map&lt;int, int&gt; indegree;
    unordered_map&lt;int, bool&gt; visited;
    unordered_map&lt;int, vector&lt;int&gt;&gt; mp;
    for (auto&amp; vect: adjacentPairs) {
        mp[vect[0]].push_back(vect[1]);
        mp[vect[1]].push_back(vect[0]);
        indegree[vect[0]]++;
        indegree[vect[1]]++;
    }
    int start = 0;
    for (auto&amp; in : indegree) 
        if (in.second == 1) {
            start = in.first;
            break;
        }
    }
    int n = indegree.size();
    vector&lt;int&gt; result;
    result.push_back(start);
    visited[start] = true;
    while (result.size() != n) {
        for (auto&amp; val : mp[start]) {
            if (!visited[val]) {
                result.push_back(val);
                visited[val] = true;
                start = val;
            }
        }
    }
    
    return result;