Отслеживание узла родителя в Depth First Search

void dfs(int v, int p) {
    if (used[v]) return;
    used[v] = true;
    for (int i = 0; i < g[v].size(); i++) 
        dfs(g[v][i], v);
}

stack<pair<int, int > > S;
while(!S.empty())
    {
        int current = S.top().second; S.pop();
        
        if(!seen[current])
        {
            seen[current] = true;
            
                        for(const auto &child : graph[current])
                S.push(make_pair(current, child);
        }
    }

for(auto &elem : graph)
    sort(elem.second.begin(), elem.second.end());

void DFS(Graph &graph)
{
    stack<int> S;
    seen_map seen, seen_parent;
    stack<size_t> next_parent;
    vector<int> parent(graph.size(), -2);
    
    for(size_t i = 0; i < graph.size(); i++)
        seen[i] = false;
    
    for(auto it = graph.begin(); it != graph.end(); ++it)
        sort(it->second.begin(), it->second.end());
    
    S.push(0);
    parent[0] = -1;
    
    while(!S.empty())
    {
        size_t current = S.top(); S.pop();
        
        if(!seen[current])
        {
            seen[current] = true;
            
            //если у вершины current всего одна смежная вершина, 
            //то она и есть родитель
            if(graph[current].size() == 1)
                parent[current] = *graph[current].begin();
            
            for(const auto &child : graph[current])
                S.push(child);
            
            //если current - не последная вершина в графе
            //если current не была ранее в стеке next_parent (костыль detected)
            if(current != graph.size()-1 && 
               seen_parent.find(current) == seen_parent.end()) 
            {   
                //пушим родителя
                next_ parent.push(current); 
                //отмечаем, что такая вершина была запушена в стек, 
                //чтоб в следующий раз такую же веришину не пушить
                seen_parent[current] = true; 
            }
        }
        //если у current еще нет родителя и ее родитель - не она сама
        else if(parent[current] == -2 && current != next_parent.top()) 
        {
            parent[current] = next_parent.top(); //фиксируем родителя для current
            next_parent.pop();
        }
    }
    
    for(const auto &elem : parent)
        cout << elem << " ";
}

vii v;
vi used, p;
int t = -1;
void dfs(int V) {
    if (used[V] != -1) return;
    used[V] = 1;
    p[V] = t++;
    forn(i, v[V].size()) {
        dfs(v[V][i]);
    }
}
 
int main() {
    int n, m;
    cin >> n >> m;
    v.resize(n);
    p.assign(n, -1);
    used.assign(n, -1);
    
    forn(i, m) {
        int a, b;
        cin >> a >> b;
        v[a].pb(b);
        v[b].pb(a);
    }
    
    forn(i, n) sort(all(v[i]));
    
    dfs(0);
    forn(i, n) cout << p[i] << " ";
    
    return 0;
}