1890F - Game of Stacks - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
#define maxx 100001

vector<int> ret(maxx),visited(maxx),stk(maxx),dfstk(maxx*10),v[maxx];
int tt;

int rt(int x)
{
    if(stk[x]==(-1))
    {
        return 1;
    }

    return 0;
}

int dfs(int cur)
{
    if(ret[cur]!=0)
    {
        return ret[cur];
    }
    if(rt(cur)==1)
    {
        return cur;
    }
    if(visited[cur]!=0)
    {
        dfstk[tt]=0;
        while(dfstk[tt]!=cur)
        {
            stk[dfstk[tt-1]]=stk[dfstk[tt-1]]-1;
            visited[dfstk[tt-1]]=0;
            tt=tt-1;
        }
        return dfs(cur);
    }
    else
    {
        visited[cur]=1;
    }
    int to=v[cur][stk[cur]];
    dfstk[tt]=cur;
    tt=tt+1;

    return dfs(to);
}

void nw(int x)
{
    while(tt!=0)
    {
        ret[dfstk[tt-1]]=x;
        tt=tt-1;
    }
}

main()
{
    int k,n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int k;
        scanf("%d",&k);
        stk[i]=k-1;
        for(int j=0;j<k;j++)
        {
            int x;
            scanf("%d",&x);
            v[i].push_back(x);
        }
    }
    for(int i=1;i<=n;i++)
    {
        int st=dfs(i);
        printf("%d%s",st,(i==n?"\n":" "));
        nw(st);
    }

    return 0;
}