Restore the Array From Adjacent Pairs solution and explanation

from collections import defaultdict

def restoreArray(adjacentPairs):
    adj_map = defaultdict(list)
    for u, v in adjacentPairs:
        adj_map[u].append(v)
        adj_map[v].append(u)

    # Find a starting point (it should have a single connection)
    start = next(k for k, v in adj_map.items() if len(v) == 1)

    # Restore the array by traversing
    res = []
    visited = set()
    current = start
    prev = None
    while current is not None:
        res.append(current)
        visited.add(current)
        neighbors = adj_map[current]
        next_node = next((n for n in neighbors if n != prev), None)
        prev = current
        current = next_node

    return res

import java.util.*;

public class Solution {
    public int[] restoreArray(int[][] adjacentPairs) {
        Map<Integer, List<Integer>> adjMap = new HashMap<>();

        // Construct the adjacency map
        for (int[] pair : adjacentPairs) {
            adjMap.putIfAbsent(pair[0], new ArrayList<>());
            adjMap.putIfAbsent(pair[1], new ArrayList<>());
            adjMap.get(pair[0]).add(pair[1]);
            adjMap.get(pair[1]).add(pair[0]);
        }

        // Find the starting point
        int start = 0;
        for (Map.Entry<Integer, List<Integer>> entry : adjMap.entrySet()) {
            if (entry.getValue().size() == 1) {
                start = entry.getKey();
                break;
            }
        }

        // Reconstruct the original array
        int[] result = new int[adjMap.size()];
        Set<Integer> visited = new HashSet<>();
        result[0] = start;
        visited.add(start);
        int prev = -1;
        for (int i = 1; i < result.length; i++) {
            List<Integer> neighbors = adjMap.get(start);
            for (int neighbor : neighbors) {
                if (!visited.contains(neighbor)) {
                    result[i] = neighbor;
                    visited.add(neighbor);
                    prev = start;
                    start = neighbor;
                    break;
                }
            }
        }

        return result;
    }
}

#include <vector>
#include <unordered_map>
#include <unordered_set>

using namespace std;

vector<int> restoreArray(vector<vector<int>>& adjacentPairs) {
    unordered_map<int, vector<int>> adjMap;
    for (const auto& pair : adjacentPairs) {
        adjMap[pair[0]].push_back(pair[1]);
        adjMap[pair[1]].push_back(pair[0]);
    }

    int start = 0;
    for (const auto& [key, neighbors] : adjMap) {
        if (neighbors.size() == 1) {
            start = key;
            break;
        }
    }

    vector<int> result;
    unordered_set<int> visited;
    int prev = -1;

    while (true) {
        result.push_back(start);
        visited.insert(start);
        auto& neighbors = adjMap[start];
        int next = -1;
        for (const auto& neighbor : neighbors) {
            if (neighbor != prev && visited.find(neighbor) == visited.end()) {
                next = neighbor;
                break;
            }
        }
        if (next == -1) break;
        prev = start;
        start = next;
    }

    return result;
}

function restoreArray(adjacentPairs) {
    const adjMap = new Map();

    // Construct the adjacency map
    for (const [u, v] of adjacentPairs) {
        if (!adjMap.has(u)) adjMap.set(u, []);
        if (!adjMap.has(v)) adjMap.set(v, []);
        adjMap.get(u).push(v);
        adjMap.get(v).push(u);
    }

    // Find the starting point
    let start;
    for (const [key, neighbors] of adjMap.entries()) {
        if (neighbors.length === 1) {
            start = key;
            break;
        }
    }

    // Reconstruct the original array
    const result = [];
    const visited = new Set();
    let prev = null;
    let current = start;

    while (current !== undefined) {
        result.push(current);
        visited.add(current);
        const neighbors = adjMap.get(current);
        const next = neighbors.find(n => n !== prev);
        prev = current;
        current = visited.has(next) ? undefined : next;
    }

    return result;
}

using System;
using System.Collections.Generic;

public class Solution {
    public int[] RestoreArray(int[][] adjacentPairs) {
        var adjMap = new Dictionary<int, List<int>>();

        // Build the adjacency map
        foreach (var pair in adjacentPairs) {
            if (!adjMap.ContainsKey(pair[0])) adjMap[pair[0]] = new List<int>();
            if (!adjMap.ContainsKey(pair[1])) adjMap[pair[1]] = new List<int>();
            adjMap[pair[0]].Add(pair[1]);
            adjMap[pair[1]].Add(pair[0]);
        }

        // Find the start of the array
        int start = 0;
        foreach (var kvp in adjMap) {
            if (kvp.Value.Count == 1) {
                start = kvp.Key;
                break;
            }
        }

        // Reconstruct the array
        List<int> result = new List<int>();
        HashSet<int> visited = new HashSet<int>();
        int prev = -1;

        while (true) {
            result.Add(start);
            visited.Add(start);
            var neighbors = adjMap[start];
            int next = -1;
            foreach (var neighbor in neighbors) {
                if (neighbor != prev && !visited.Contains(neighbor)) {
                    next = neighbor;
                    break;
                }
            }
            if (next == -1) break;
            prev = start;
            start = next;
        }

        return result.ToArray();
    }
}

func restoreArray(adjacentPairs [][]int) []int {
	n := len(adjacentPairs) + 1
	g := map[int][]int{}
	for _, e := range adjacentPairs {
		a, b := e[0], e[1]
		g[a] = append(g[a], b)
		g[b] = append(g[b], a)
	}
	ans := make([]int, n)
	for k, v := range g {
		if len(v) == 1 {
			ans[0] = k
			ans[1] = v[0]
			break
		}
	}
	for i := 2; i < n; i++ {
		v := g[ans[i-1]]
		ans[i] = v[0]
		if v[0] == ans[i-2] {
			ans[i] = v[1]
		}
	}
	return ans
}